Discrete Mathematics and Theoretical Computer Science: 4th International Conference, DMTCS 2003, Dijon, France, July 7-12, 2003. Proceedings (Lecture Notes in Computer Science, 2731)

Lecture Notes in Computer Science
Preface
Table of Contents
Two Philosophical Applications of Algorithmic Information Theory
	Introduction. Why Is Program Size of Philosophical Interest?
	Is Mathematics Empirical or Is It a priori?
		Einstein: Math Is Empirical
		G\"odel: Math Is a priori
		AIT: Math Is Quasi-empirical
	How Can We Partition the World into Distinct Entities?
	Conclusion and Future Prospects
Covering and Secret Sharing with Linear Codes
	Introduction
	A Link between Secret Sharing Schemes and Linear Codes
	The Access Structure of the Secret Sharing Schemes Based on Linear Codes
	Characterisations of Minimal Codewords
		Sufficient Condition from Weights
		Sufficient and Necessary Condition Using Exponential Sums
	Bounds on Exponential Sums
	Secret Sharing Schemes from Irreducible Cyclic Codes
		The General Case
		The Semi-primitive Case
	Secret Sharing Schemes from Quadratic Form Codes
	Secret Sharing Schemes from Another Class of Codes
		A Generalisation of a Class of Linear Codes
	Conclusion and Remarks
Combinatorial Problems Arising in SNP and Haplotype Analysis
	Introduction
	The Haplotype Phasing Problem
		Clark\'s Rule
		Maximum Likelihood
		Clark\'s Rule and Population Models
		Parsimony Formulations
		Perfect Phylogeny
	Haplotype Assembly
	Haplotype Block Detection
	SNP Selection
	Discussion
Cellular Automata and Combinatoric Tilings in Hyperbolic Spaces. A Survey
	Introduction
	An Abstract on Hyperbolic Geometry
		Lines of the Hyperbolic Plane and Angles
		Reflections in a $h$-Line
	The Splitting Method: Combinatoric Tilings
		The Geometric Part
		The Algebraic Part
		The Classical Case: The Pentagrid
	New Results in the Hyperbolic Plane
		Revisiting Poincar\'e\'s Theorem
		Tessellations by Regular Polygons
	Complexity Classes for Hyperbolic CA\'s
	Higher Dimensions
		The 3D Case
		The 4D Case
	Infinigons and Infinigrids
Generating Gray Codes in O(1) Worst-Case Time per Word
	Definition of a Gray Code
	Non-recursive Description of a Word-List in Generalized Lexicographical Order
	The Bitner-Ehrlich-Reingold Method of Finding the Successor of a Word in $O(1)$Worst-Case Time
	A Generalized Version of the Bitner-Ehrlich-Reingold Method that Works on almost All Gray Codes
Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems
	Introduction
	Basis Structure for Dual {em LI(2)}
	The Algorithm
	Unbounded Polyhedra
	Complexity Analysis
	Conclusion
Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata
	Introduction and Preliminaries
	Genericity and Baire Category
	Bounded Automatic Genericity
	The Diagonalization Strength of Bounded Automated Genericity
	Unbounded Automatic Genericity
On the Order Dual of a Riesz Space
	Basic Definitions and Notation
	Positive Functionals
	The Order Dual
	The Order Dual of a Riesz Space with Unit
A Finite Complete Set of Equations Generating Graphs
	Introduction
	Magmoids
	Permutation Patterns and Discrete Graph Patterns
	Graph Patterns
	Related Literature
ECO Method and the Exhaustive Generation of Convex Polyominoes
	Introduction
		ECO Method
		Succession Rules
	An ECO Operator for the Class of Convex Polyominoes
		The Succession Rule
	Exhaustive Generation Using the ECO Method
		A CAT Algorithm for the Generation of Convex-Polyominoes
		Further Work
Regular Expressions with Timed Dominoes
	Introduction
	Timed Automata and Timed Regular Expressions
	Timed Words with Distinguished Points = Timed $n$-Words
		Timed Regminoes, Timed Regwords, and Regular Expressions over Them
	Checking $2n$-Timed Regular Expressions for Emptiness
	Combining the Timing and the Untimed Representations
	Conclusions
On Infinitary Rational Relations and Borel Sets
	Introduction
	Infinitary Rational Relations
	Borel Sets
	${bf Sigma ^0_3}$-Complete Infinitary Rational Relations
	${bf Pi ^0_3}$-Complete Infinitary Rational Relations
Efficient Algorithms for Disjoint Matchings among Intervals and Related Problems
	Introduction
	Preliminaries
	Disjoint Matchings among Intervals
	Perfect Disjoint Multidimensional Matchings
On Functions and Relations
	Introduction
	Preliminaries
	General Results
	Operators on Function and Relation Classes
	The Inclusion Structure and Structural Consequences
Paths Coloring Algorithms in Mesh Networks
	Introduction
		Related Previous Work
		Summary of Results
	Notations
	Coloring $LC$-Routings
	Coloring $(alpha ,beta )$ $LC$-Routings
	Coloring $LC$-Routings on the Toroidal Mesh
	Coloring $(LC,CL)$-Routings
	Conclusions
Finite State Strategies in One Player McNaughton Games
	Introduction and Basic Concepts
	One Player Games and Strategies
	Deciding One Player Games
	Finite State Strategies and Structure
	Conclusion
On Algebraic Expressions of Series-Parallel and Fibonacci Graphs
	Introduction
	Algebraic Expressions of Series-Parallel Graphs
	Algebraic Expressions of Fibonacci Graphs
	Applying St-dag Expressions to a Symbolic Solution of the Shortest Path Problem
	Conclusions
Boolean NP-Partitions and Projective Closure
	Introduction
	Preliminaries
	Representing Partitions and Partition Classes
	Mind-Change Complexity of Projection Classes
	Partition Classes Given in Free Representations
	Partition Classes Given in Bound Representations
	Algorithmic Issues Related to the Projective Closure
On Unimodality of Independence Polynomials of Some Well-Covered Trees
	Introduction
	Preliminary Results
	Independence Polynomials of Well-Covered Spiders
	Independence Polynomials of Some More Well-Covered Trees
	Conclusions
A Coloring Algorithm for Finding Connected Guards in Art Galleries
	Introduction
	An Algorithm
	Main Theorem
	Orthogonal Art Galleries
An Analysis of Quantified Linear Programs
	Introduction
	Problem Statement
	The Quantifier Elimination Algorithm
	Correctness and Analysis
	A Taxonomy of QLPs
An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique*
	Introduction
	Preliminaries
	Maximum Clique Algorithm MCQ
		A Basic Algorithm
		Pruning
		Initial Sorting and Simple Numbering
	Computational Experiments
		Results for Random Graphs
		Results for DIMACS Benchmark Graphs
	Conclusions
On the Monotonic Computability of Semi-computable Real Numbers
	Introduction
	Preliminaries
	Monotonic Computability vs Semi-computability
	Monotonic Computability vs Computability
Author Index