Logical aspects of Cayley-graphs: the group case

DOI10.1016/J.APAL.2004.06.002MaRDI QIDQ705541zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3873585 (Why is no real title available?)
• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 3917707 (Why is no real title available?)
• scientific article; zbMATH DE number 4076625 (Why is no real title available?)
• scientific article; zbMATH DE number 1375581 (Why is no real title available?)
• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 3510287 (Why is no real title available?)
• scientific article; zbMATH DE number 3537224 (Why is no real title available?)
• scientific article; zbMATH DE number 3559545 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 1059319 (Why is no real title available?)
• scientific article; zbMATH DE number 1086492 (Why is no real title available?)
• scientific article; zbMATH DE number 1962836 (Why is no real title available?)
• scientific article; zbMATH DE number 1929935 (Why is no real title available?)
• scientific article; zbMATH DE number 3805807 (Why is no real title available?)
• scientific article; zbMATH DE number 2102748 (Why is no real title available?)
• scientific article; zbMATH DE number 2102749 (Why is no real title available?)
• scientific article; zbMATH DE number 863496 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3381557 (Why is no real title available?)
• A NOTE ON THE EXISTENTIAL THEORY OF EQUATIONS IN PLAIN GROUPS
• Alternation
• An algebraic characterization of groups with soluble word problem
• An effective version of Stallings' theorem in the case of context-free groups
• Automorphism groups of context-free graphs
• CAYLEY GRAPHS OF VIRTUALLY FREE GROUPS
• Canonical representatives and equations in hyperbolic groups
• Cutting up graphs
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Deterministic dynamic logic is strictly weaker than dynamic logic
• Domino Treewidth
• Existential and positive theories of equations in graph products
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Graph minors. II. Algorithmic aspects of tree-width
• Graphs and groups with tree-like properties
• Group presentations, formal languages and characterizations of one- counter groups
• Groups and Simple Languages
• Groups and graphs: Groups acting on trees, ends, and cancellation diagrams
• Groups, the theory of ends, and context-free languages
• On Dehn's algorithm
• On infinite transition graphs having a decidable monadic theory
• On the regular structure of prefix rewriting
• Some results on tree decomposition of graphs
• Subgroups of finitely presented groups
• The accessibility of finitely presented groups
• The computational complexity of logical theories
• 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
• The monadic theory of order
• The structure of the models of decidable monadic theories of graphs
• The theory of ends, pushdown automata, and second-order logic
• Upper bounds to the clique width of graphs
• Vertex-transitive graphs and accessibility

Cited in

(31)

• Subshifts, Languages and Logic
• scientific article; zbMATH DE number 4076625 (Why is no real title available?)
• scientific article; zbMATH DE number 1962836 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 848090 (Why is no real title available?)
• Groups, graphs, languages, automata, games and second-order monadic logic
• Cayley graphs as classifiers for data mining: the influence of asymmetries
• Geometric characterizations of virtually free groups
• 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
• From automatic structures to automatic groups.
• Tree-partitions with bounded degree trees
• scientific article; zbMATH DE number 7561314 (Why is no real title available?)
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Vertex separators, chordality and virtually free groups
• On Cayley graphs of virtually free groups.
• When Is a Graph Product of Groups Virtually-Free?
• scientific article; zbMATH DE number 7561690 (Why is no real title available?)
• The large scale geometry of strongly aperiodic subshifts of finite type
• Solutions to twisted word equations and equations in virtually free groups
• Graphs of linear growth have bounded treewidth
• 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)