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

DOI10.1142/S0218196712500610MaRDI QIDQ4902680zbMATH OpenOpenAlexFDO

Authors Alan J. Cain, Victor Maltcev

Publication date 17 January 2013

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

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

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)

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).

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Automatic semigroups
• Hyperbolic groups and completely simple semigroups.
• INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS
• On the definition of word hyperbolic groups.
• Word hyperbolic semigroups

Cited in

(8)

• A language hierarchy of binary relations
• On the word problem for special monoids
• Decision problems for word-hyperbolic semigroups
• A strong geometric hyperbolicity property for directed graphs and monoids.
• Markov semigroups, monoids and groups.
• 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)