Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht

On the work of Andrzej Ehrenfeucht in model theory....Pages 1-13
Syntax vs. semantics on finite structures....Pages 14-33
Expressive power of unary counters....Pages 34-50
Some strange quantifiers....Pages 51-65
Pebble games in model theory....Pages 66-83
An interpretive isomorphism between binary and ternary relations....Pages 84-105
Vagueness — A rough set view....Pages 106-117
Ehrenfeucht games, the composition method, and the monadic theory of ordinal words....Pages 118-143
Monadic second order logic and node relations on graphs and trees....Pages 144-161
Approximating the volume of general Pfaffian bodies....Pages 162-173
Complement-equivalence classes on graphs....Pages 174-191
On compact directed acyclic word graphs....Pages 192-211
Metric entropy and minimax risk in classification....Pages 212-235
Of periods, quasiperiods, repetitions and covers....Pages 236-248
Combinatorics of standard Sturmian words....Pages 249-267
Compactness of systems of equations on completely regular semigroups....Pages 268-280
Decision problems concerning algebraic series with noncommuting variables....Pages 281-290
Associative shuffle of infinite words....Pages 291-307
Constructing sequential bijections....Pages 308-321
Rewriting rules for synchronization languages....Pages 322-338
DNA sequence classification using DAWGs....Pages 339-352
DNA computing: Distributed splicing systems....Pages 353-370