The theory of ends, pushdown automata, and second-order logic

DOI10.1016/0304-3975(85)90087-8zbMath0605.03005OpenAlexW1971416129MaRDI QIDQ1084096

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90087-8

zbMATH Keywords

finiteness cellular automata decision problems membership problem infinity transition graph pushdown automata inclusion problem tiling systems automata theory of ends Cayley graphs of context-free groups context-free graphs decidable monadic second-order theory reachability sets of vector addition systems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Cellular automata (computational aspects) (68Q80) Decidability of theories and sets of sentences (03B25) Combinatorial aspects of tessellation and tiling problems (05B45) Turing machines and related notions (03D10)

Related Items

Geometric characterizations of virtually free groups, WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM, Automatic graphs and D0L-sequences of finite graphs, Self-avoiding walks and multiple context-free languages, Word problems of groups: formal languages, characterizations and decidability, Modular strategies for recursive game graphs, Complexity results on branching-time pushdown model checking, Model-checking CTL* over flat Presburger counter systems, Marking shortest paths on pushdown graphs does not preserve MSO decidability, Model Checking Procedural Programs, Synchronization of Regular Automata, Linearly bounded infinite graphs, Inverse monoids: decidability and complexity of algebraic questions., The monadic second-order logic of graphs, II: Infinite graphs of bounded width, ON GROUPS WHICH ARE SYNTACTIC MONOIDS OF DETERMINISTIC CONTEXT-FREE LANGUAGES, On the word problem for special monoids, On groups whose word problem is solved by a counter automaton., The language of self-avoiding walks, Graphes canoniques de graphes algébriques, The isomorphism problem for finite extensions of free groups is in PSPACE, Set-theoretic graph rewriting, Cellular automata between sofic tree shifts, A counterexample to Thiagarajan's conjecture on regular event structures, ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS, Vertex separators, chordality and virtually free groups, Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions, On the transition graphs of Turing machines., Complete SAT-Based Model Checking for Context-Free Processes, Properties and limits of recognition of sets of integers by countable automata, On systems of equations defining infinite graphs, Monadic second-order logic and the domino problem on self-similar graphs, Unnamed Item, Groups, graphs, languages, automata, games and second-order monadic logic, Context-free pairs of groups. I: Context-free pairs and graphs, On a class of poly-context-free groups generated by automata, A Hierarchy of Automaticω-Words having a Decidable MSO Theory, About the Domino Problem for Subshifts on Groups, Model checking the full modal mu-calculus for infinite sequential processes, Growth-sensitivity of context-free languages., An Infinite Automaton Characterization of Double Exponential Time, EQUATIONS IN FREE INVERSE MONOIDS, Context-free pairs of groups. II: Cuts, tree sets, and random walks, An effective version of Stallings' theorem in the case of context-free groups, COMPLETE SAT-BASED MODEL CHECKING FOR CONTEXT-FREE PROCESSES, Automorphism groups of context-free graphs, The large scale geometry of strongly aperiodic subshifts of finite type, Alternating automata, the weak monadic theory of trees and its complexity, Decidability of bisimulation equivalence for normed pushdown processes, On complexity functions of infinite words associated with generalized Dyck languages, On the regular structure of prefix rewriting, Infinite hypergraphs. II: Systems of recursive equations, Partially commutative inverse monoids., Unnamed Item, Unnamed Item, Verification of qualitative \(\mathbb Z\) constraints, Amalgams of finite inverse semigroups and deterministic context-free languages., The modular decomposition of countable graphs. Definition and construction in monadic second-order logic, CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES, Pushdown module checking, Group presentations, formal languages and characterizations of one- counter groups, An Automata-Theoretic Approach to Infinite-State Systems, Logical aspects of Cayley-graphs: the group case, Pushdown automata, multiset automata, and Petri nets, Deciding bisimulation-like equivalences with finite-state processes, On the Petri net realization of context-free graphs, Families of automata characterizing context-sensitive languages, Space Complexity and Word Problems of Groups, On Cayley graphs of basic algebraic structures, On mathematical contributions of Paul E. Schupp, Unnamed Item, Unnamed Item, Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems, Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems, Note on winning positions on pushdown games with \(\omega\)-regular conditions, DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS, Infinite hypergraphs. I: Basic properties, Optimally Resilient Strategies in Pushdown Safety Games, The Reachability Problem over Infinite Graphs, Decidability of bisimulation equivalence for normed pushdown processes, Context-free event domains are recognizable, Model Checking FO(R) over One-Counter Processes and beyond, LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE, On the complexity of a family of \(k\)-context-free sequences, Embeddings into Thompson's group V and coCF groups, Context-free event domains are recognizable, Free products in R. Thompson’s group 𝑉, GROUPS WITH INDEXED CO-WORD PROBLEM, Model checking the full modal mu-calculus for infinite sequential processes, When Is a Graph Product of Groups Virtually-Free?, On infinite transition graphs having a decidable monadic theory, Pushdown processes: Games and model-checking, Simulation preorder over simple process algebras, Reflections on a Geometry of Processes, GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM, Shelah-Stupp's and Muchnik's iterations revisited, Growth and ergodicity of context-free languages

Cites Work