Groups, graphs, languages, automata, games and second-order monadic logic

DOI10.1016/j.ejc.2012.03.010zbMath1269.68060arXiv1201.3108OpenAlexW2045644373MaRDI QIDQ444388

Francesca Fiorenzi, Paul E. Schupp, Michel Coornaert, Tullio G. Ceccherini Silberstein

Publication date: 14 August 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.3108

zbMATH Keywords

group presentationsgroupscellular automatamonadic second-order logicCayley graphsdecidabilityfinite automatainfinite gamesformal languagestree automatagrammarspushdown automatainfinite treesword problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Logic in computer science (03B70) Cellular automata (computational aspects) (68Q80) Decidability of theories and sets of sentences (03B25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (3)

Language acceptability of finite automata based on theory of semi‐tensor product of matrices ⋮ Multipass automata and group word problems ⋮ CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Context-free pairs of groups. I: Context-free pairs and graphs
• Context-free pairs of groups. II: Cuts, tree sets, and random walks
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Groups, the theory of ends, and context-free languages
• On accessibility of groups
• Reversibility of 2D cellular automata is undecidable
• On the growth of linear languages
• Gardens of Eden and amenability on cellular automata
• Graphs and groups with tree-like properties
• A course in formal languages, automata and groups
• The domino problem of the hyperbolic plane is undecidable
• The accessibility of finitely presented groups
• The theory of ends, pushdown automata, and second-order logic
• Alternating automata on infinite trees
• Groups and graphs: Groups acting on trees, ends, and cancellation diagrams
• Borel determinacy
• Undecidable tiling problems in the hyperbolic plane
• An example of an indexed language of intermediate growth
• Amenable groups and cellular automata
• Endomorphisms of symbolic algebraic varieties
• Reversibility and surjectivity problems of cellular automata
• Fixed sets and free subgroups of groups acting on metric spaces
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• On the entropy of regular languages.
• Growth-sensitivity of context-free languages.
• Context-free languages of sub-exponential growth
• Theory of cellular automata: a survey
• Some groups having only elementary actions on metric spaces with hyperbolic boundaries.
• Undecidability and nonperiodicity for tilings of the plane
• Small cancellation theory over free products with amalgamation
• On torsion-free groups with infinitely many ends
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Enden offener Räume und unendliche diskontinuierliche Gruppen
• Growth and ergodicity of context-free languages
• THE WORD PROBLEM
• Subgroups of finitely presented groups
• Growth and ergodicity of context-free languages II: The linear case
• Cellular Automata and Groups
• Groups and Simple Languages
• Finiteness Conditions on Subgroups and Formal Language Theory
• Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems
• Descriptive set theory and harmonic analysis
• Unforgettable Forgetful Determinacy
• Free Subgroups of Groups with Nontrivial Floyd Boundary
• An effective version of Stallings' theorem in the case of context-free groups
• Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Three models for the description of language
• Some results on one-relator groups
• Endomorphisms and automorphisms of the shift dynamical system
• On the entropy of context-free languages
• The undecidability of the domino problem
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• The growth function of context-free languages

This page was built for publication: Groups, graphs, languages, automata, games and second-order monadic logic