LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE

DOI10.1142/S0218196706003001MaRDI QIDQ5483463zbMATH OpenFDO

Authors Markus Lohrey, Dietrich Kuske

Publication date 14 August 2006

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

Full work available at URL https://doi.org/10.1142/S0218196706003001

zbMATH Keywords

Cayley graphsdecidable theoriesgraph products of monoids

Mathematics Subject Classification ID

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

Recommendations

• Logical aspects of Cayley-graphs: the group case
• The Cayley-graph of the queue monoid: logic and decidability
• Finite presentability and isomorphism of Cayley graphs of monoids
• On monoid graphs
• On graph products of monoids
• Cayley Digraphs of Finite Abelian Groups and Monomial Ideals
• scientific article; zbMATH DE number 1962836
• On Cayley graphs of semilattices of semigroups.
• scientific article; zbMATH DE number 906518
• Graphs and ranks of monoids

Cites work

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

Cited in

(14)

• Logical aspects of Cayley-graphs: the group case
• scientific article; zbMATH DE number 1962836 (Why is no real title available?)
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Closure properties of knapsack semilinear groups
• Knapsack in graph groups
• WORD EQUATIONS OVER GRAPH PRODUCTS
• Groups, graphs, languages, automata, games and second-order monadic logic
• Cayley graphs as classifiers for data mining: the influence of asymmetries
• Inverse monoids: decidability and complexity of algebraic questions.
• The power word problem in graph products
• scientific article; zbMATH DE number 7561314 (Why is no real title available?)
• Finite presentability and isomorphism of Cayley graphs of monoids
• MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS
• On decidability of list structures

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

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