Context-free rewriting systems and word-hyperbolic structures with uniqueness

DOI10.1142/S0218196712500610zbMATH Open1284.68320arXiv1201.6616OpenAlexW3099396151MaRDI QIDQ4902680FDOQ4902680

Authors: Alan J. Cain, Victor Maltcev 

Publication date: 17 January 2013

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

Abstract: This paper proves that any monoid presented by a confluent context-free monadic rewriting system is word-hyperbolic. This result then applied to answer a question asked by Duncan & Gilman by exhibiting an example of a word-hyperbolic monoid that does not admit a word-hyperbolic structure with uniqueness (that is, in which the language of representatives maps bijectively onto the monoid).

Full work available at URL: https://arxiv.org/abs/1201.6616

Recommendations

• Hyperbolicity of monoids presented by confluent monadic rewriting systems.
• INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS
• MONOIDS PRESENTED BY REWRITING SYSTEMS AND AUTOMATIC STRUCTURES FOR THEIR SUBMONOIDS
• Publication:3026992
• About the descriptive power of certain classes of finite string-rewriting systems

zbMATH Keywords

uniquenessstring rewriting systemcontext-freeword-hyperbolic monoid

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• On the definition of word hyperbolic groups.
• Automatic semigroups
• Hyperbolic groups and completely simple semigroups.
• Word hyperbolic semigroups
• INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS

Cited In (8)

• A language hierarchy of binary relations
• On the word problem for special monoids
• Decision problems for word-hyperbolic semigroups
• Markov semigroups, monoids and groups.
• A strong geometric hyperbolicity property for directed graphs and monoids.
• MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS
• Finitely presented monoids with linear Dehn function need not have regular cross-sections.
• Growths of endomorphisms of finitely generated semigroups

This page was built for publication: Context-free rewriting systems and word-hyperbolic structures with uniqueness

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