Logical aspects of Cayley-graphs: the group case

DOI10.1016/j.apal.2004.06.002zbMath1063.03005OpenAlexW1976522318MaRDI QIDQ705541

Markus Lohrey, Dietrich Kuske

Publication date: 31 January 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.06.002

zbMATH Keywords

Cayley graphword problemdecidabilitycontext-free groupsmonadic second-order theory

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (23)

Geometric characterizations of virtually free groups ⋮ On Cayley graphs of virtually free groups ⋮ Inverse monoids: decidability and complexity of algebraic questions. ⋮ Subshifts as models for MSO logic ⋮ ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS ⋮ Vertex separators, chordality and virtually free groups ⋮ Graphs of linear growth have bounded treewidth ⋮ Graph subshifts ⋮ Poorly connected groups ⋮ About the Domino Problem for Subshifts on Groups ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ The large scale geometry of strongly aperiodic subshifts of finite type ⋮ CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES ⋮ From automatic structures to automatic groups. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Subshifts, Languages and Logic ⋮ On tree-partition-width ⋮ LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE ⋮ Cayley graphs as classifiers for data mining: the influence of asymmetries ⋮ When Is a Graph Product of Groups Virtually-Free? ⋮ Rational subsets and submonoids of wreath products.

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
• Automorphism groups of context-free graphs
• On the regular structure of prefix rewriting
• Existential and positive theories of equations in graph products
• Groups, the theory of ends, and context-free languages
• The structure of the models of decidable monadic theories of graphs
• Graphs and groups with tree-like properties
• The accessibility of finitely presented groups
• The theory of ends, pushdown automata, and second-order logic
• Groups and graphs: Groups acting on trees, ends, and cancellation diagrams
• Group presentations, formal languages and characterizations of one- counter groups
• The monadic theory of order
• The computational complexity of logical theories
• Vertex-transitive graphs and accessibility
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Cutting up graphs
• On infinite transition graphs having a decidable monadic theory
• Canonical representatives and equations in hyperbolic groups
• Upper bounds to the clique width of graphs
• On Dehn's algorithm
• CAYLEY GRAPHS OF VIRTUALLY FREE GROUPS
• Subgroups of finitely presented groups
• Deterministic dynamic logic is strictly weaker than dynamic logic
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Groups and Simple Languages
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Graph minors. II. Algorithmic aspects of tree-width
• Alternation
• An algebraic characterization of groups with soluble word problem
• Domino Treewidth
• An effective version of Stallings' theorem in the case of context-free groups
• A NOTE ON THE EXISTENTIAL THEORY OF EQUATIONS IN PLAIN GROUPS
• Some results on tree decomposition of graphs
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: Logical aspects of Cayley-graphs: the group case