Discrete Mathematics and Theoretical Computer Science: 4th International Conference, DMTCS 2003 Dijon, France, July 7–12, 2003 Proceedings

Gregory Chaitin (auth.), Cristian S. Calude, Michael J. Dinneen, Vincent Vajnovszki (eds.)3540405054, 9783540405054

This book constitutes the refereed proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science, DMTCS 2003, held in Dijon, France in July 2003.

The 18 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 35 submissions. A broad variety of topics in discrete mathematics and the theory of computing is addressed including information theory, coding, algorithms, complexity, automata, computational mathematics, combinatorial computations, graph computations, algorithmic geometry, relational methods, game-theoretic methods, combinatorial optimization, finite state systems, etc.

---

Table of contents :
Two Philosophical Applications of Algorithmic Information Theory….Pages 1-10
Covering and Secret Sharing with Linear Codes….Pages 11-25
Combinatorial Problems Arising in SNP and Haplotype Analysis….Pages 26-47
Cellular Automata and Combinatoric Tilings in Hyperbolic Spaces. A Survey….Pages 48-72
Generating Gray Codes in O (1) Worst-Case Time per Word….Pages 73-88
Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems….Pages 89-96
Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata….Pages 97-108
On the Order Dual of a Riesz Space….Pages 109-117
A Finite Complete Set of Equations Generating Graphs….Pages 118-128
ECO Method and the Exhaustive Generation of Convex Polyominoes….Pages 129-140
Regular Expressions with Timed Dominoes….Pages 141-154
On Infinitary Rational Relations and Borel Sets….Pages 155-167
Efficient Algorithms for Disjoint Matchings among Intervals and Related Problems….Pages 168-180
On Functions and Relations….Pages 181-192
Paths Coloring Algorithms in Mesh Networks….Pages 193-202
Finite State Strategies in One Player McNaughton Games….Pages 203-214
On Algebraic Expressions of Series-Parallel and Fibonacci Graphs….Pages 215-224
Boolean NP-Partitions and Projective Closure….Pages 225-236
On Unimodality of Independence Polynomials of Some Well-Covered Trees….Pages 237-256
A Coloring Algorithm for Finding Connected Guards in Art Galleries….Pages 257-264
An Analysis of Quantified Linear Programs….Pages 265-277
An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique….Pages 278-289
On the Monotonic Computability of Semi-computable Real Numbers….Pages 290-300