Application of model theoretic games to discrete linear orders and finite automata
From MaRDI portal
Publication:4168070
DOI10.1016/S0019-9958(77)90443-0zbMath0387.68037MaRDI QIDQ4168070
Publication date: 1977
Published in: Information and Control (Search for Journal in Brave)
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Graph theory (05C99) Total orders (06A05)
Related Items
Towards a language theory for infinite N-free pomsets., On the Ehrenfeucht-Fraïssé game in theoretical computer science, Zero-one laws with variable probability, Regular sets of infinite message sequence charts, On uniformity within \(NC^ 1\), Semigroups and languages of dot-depth two, A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I, A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II, Annual Meeting of the Association for Symbolic Logic, Los Angeles, 1989, Algorithmic uses of the Feferman-Vaught theorem, Inclusion relations between some congruences related to the dot-depth hierarchy, The dimension of the negation of transitive closure, Extensions of an idea of McNaughton, First-order logic on finite trees, The Algebraic Counterpart of the Wagner Hierarchy, Model-checking hierarchical structures, Schützenberger and Eilenberg theorems for words on linear orderings, On the translation of automata to linear temporal logic, Fixpoint logics over hierarchical structures, Quantitative vs. weighted automata, On the structure of random unlabelled acyclic graphs., Characterizations of fuzzy finite automata., FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES, Classifying regular events in symbolic logic, On weighted first-order logics with discounting, Modal functions for concise definition of state machines and products, Logically defined subsets of \(\mathbb{N}{}^ k\), Monadic partition logics and finite automata, A Practical Approach to Courcelle's Theorem, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Ehrenfeucht-Fraïssé goes automatic for real addition, Logic and rational languages of words indexed by linear orderings, Logic, semigroups and automata on words, Games, equations and the dot-depth hierarchy, On distinguishing sets of structures by first-order sentences of minimal quantifier rank, On the definability of properties of finite graphs, Star-free sets of words on ordinals, Computational Semantics for Monadic Quantifiers, On the expressive power of temporal logic for infinite words, Logic over words on denumerable ordinals, Query automata over finite trees, Expressibility of output equals input. Negative and positive results
