LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE

DOI10.1142/S0218196706003001zbMath1151.03003MaRDI QIDQ5483463

Markus Lohrey, Dietrich Kuske

Publication date: 14 August 2006

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

Cayley graphsdecidable theoriesgraph products of monoids

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) 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)

Related Items

Inverse monoids: decidability and complexity of algebraic questions. ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ Knapsack in graph groups ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Closure properties of knapsack semilinear groups ⋮ COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS ⋮ Unnamed Item ⋮ Cayley graphs as classifiers for data mining: the influence of asymmetries ⋮ On decidability of list structures

Cites Work

• Unnamed Item
• Logical aspects of Cayley-graphs: the group case
• Groups, the theory of ends, and context-free languages
• A uniform method for proving lower bounds on the computational complexity of logical theories
• The theory of ends, pushdown automata, and second-order logic
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• Groups and graphs: Groups acting on trees, ends, and cancellation diagrams
• The complexity of logical theories
• The monadic theory of order
• Algorithms and geometry for graph products of groups
• Automatic semigroups
• Monadic second-order logic on tree-like structures
• Extensions and submonoids of automatic monoids.
• A combinatorial property and Cayley graphs of semigroups
• On transitive Cayley graphs of groups and semigroups
• Combinatorial problems of commutation and rearrangements
• On theories with a combinatorial definition of 'equivalence'
• GRAPH PRODUCTS AND CANNON PAIRS
• On graph products of automatic monoids
• Confluent and Other Types of Thue Systems
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Impossibility of an algorithm for the decision problem in finite classes
• Graph products of monoids

This page was built for publication: LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE