Structures in Logic and Computer Science: A Selection of Essays in Honor of A. EhrenfeuchtJan Mycielski, Grzegorz Rozenberg, Arto Salomaa This book is dedicated to Andrzej Ehrenfeucht on the occasion of his 65th birthday. On personal invitation by the volume editors, 22 internationally well-known scientists from mathematical logics and theoretical computer science participated in this project honoring an excellent scientist with excellent papers centered around his scientific work. The 22 invited papers are presented in topical sections on model theory, games and logic, graphs and algorithms, pattern matching and learning, combinatorics of words, algebra of languages, formal language theory, and computational molecular biology. |
Contents
I | 1 |
II | 14 |
III | 34 |
IV | 51 |
V | 66 |
VI | 84 |
VII | 106 |
VIII | 118 |
XIV | 236 |
XV | 249 |
XVI | 268 |
XVII | 281 |
XVIII | 291 |
XIX | 308 |
XX | 322 |
XXI | 339 |
Other editions - View all
Structures in Logic and Computer Science Jan Mycielski,Grzegorz Rozenberg,Arto Salomaa No preview available - 2014 |
Common terms and phrases
a₁ algebra algorithm alphabet applied automata axiomatizable axiomatizable classes bijection binary relation bound c.r. semigroups CDAWG characterization closure component Computer Science construction Corollary database DAWG defined definition denoted distribution edges Ehrenfeucht Ehrenfeucht game elements equivalent example existential exon finite models finite set finite structures first-order logic free monoid function Gaifman map given graph H systems Hence indiscernible induction infinite integer interpretation intron isomorphism k-types L(Ct label Lemma length linear order M₁ Math metric entropy minimax minimax risk model theory monadic monadic second-order monoid morphism MSO formula node obtained occurrences operation P₁ player prediction prefix problem Proof prove quantifiers quasiperiod Ramsey's Theorem recursive Rees matrix semigroup result rough set Salomaa satisfies CP second-order logic semantics sentence sequence string Sturmian words subset suffix tree symbols Theorem transitions unary variables VC dimension vertex w-trajectories w-word w₁