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

by Dmtcs 200 (2003 Dijon, France); Calude, Cristian; Dinneen, M. J.; Vajnovszki, Vincent

• ISBN13: 9783540405054
• ISBN10: 3540405054
• Format: Paperback
• Copyright: 2003-08-01
• Publisher: Springer Verlag

Summary

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	p. 1
Covering and Secret Sharing with Linear Codes	p. 11
Combinatorial Problems Arising in SNP and Haplotype Analysis	p. 26
Cellular Automata and Combinatoric Tilings in Hyperbolic Spaces. A Survey	p. 48
Generating Gray Codes in O(1) Worst-Case Time per Word	p. 73
Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems	p. 89
Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata	p. 97
On the Order Dual of a Riesz Space	p. 109
A Finite Complete Set of Equations Generating Graphs	p. 118
ECO Method and the Exhaustive Generation of Convex Polyominoes	p. 129
Regular Expressions with Timed Dominoes	p. 141
On Infinitary Rational Relations and Borel Sets	p. 155
Efficient Algorithms for Disjoint Matchings among Intervals and Related Problems	p. 168
On Functions and Relations	p. 181
Paths Coloring Algorithms in Mesh Networks	p. 193
Finite State Strategies in One Player McNaughton Games	p. 203
On Algebraic Expressions of Series-Parallel and Fibonacci Graphs	p. 215
Boolean NP-Partitions and Projective Closure	p. 225
On Unimodality of Independence Polynomials of Some Well-Covered Trees	p. 237
A Coloring Algorithm for Finding Connected Guards in Art Galleries	p. 257
An Analysis of Quantified Linear Programs	p. 265
An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique	p. 278
On the Monotonic Computability of Semi-computable Real Numbers	p. 290
Author Index	p. 301
Table of Contents provided by Blackwell. All Rights Reserved.