Logical aspects of Cayley-graphs: the group case

DOI10.1016/J.APAL.2004.06.002zbMATH Open1063.03005OpenAlexW1976522318MaRDI QIDQ705541FDOQ705541

Authors: Dietrich Kuske, Markus Lohrey 

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

Recommendations

• scientific article; zbMATH DE number 1962836
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Groups, graphs, languages, automata, games and second-order monadic logic
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Developments in Language Theory

zbMATH Keywords

Cayley graphdecidabilityword problemcontext-free groupsmonadic second-order theory

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (31)

• Subshifts, Languages and Logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Product structure of graph classes with bounded treewidth
• Graph subshifts
• Developments in Language Theory
• About the domino problem for subshifts on groups
• Why do mathematicians need different ways of presenting mathematical objects? The case of Cayley graphs
• On tree-partition-width
• Title not available (Why is that?)
• Geometric characterizations of virtually free groups
• Groups, graphs, languages, automata, games and second-order monadic logic
• Cayley graphs as classifiers for data mining: the influence of asymmetries
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Inverse monoids: decidability and complexity of algebraic questions.
• Context-free groups and their structure trees.
• Poorly connected groups
• An automata theoretic approach to the generalized word problem in graphs of groups.
• ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS
• Tree-partitions with bounded degree trees
• From automatic structures to automatic groups.
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Title not available (Why is that?)
• Vertex separators, chordality and virtually free groups
• On Cayley graphs of virtually free groups.
• When Is a Graph Product of Groups Virtually-Free?
• Title not available (Why is that?)
• The large scale geometry of strongly aperiodic subshifts of finite type
• Graphs of linear growth have bounded treewidth
• Solutions to twisted word equations and equations in virtually free groups
• Subshifts as models for MSO logic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705541)