Notions of hyperbolicity in monoids.

DOI10.1016/J.TCS.2009.10.016MaRDI QIDQ846368zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 9 February 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.10.016

zbMATH Keywords

automatic monoidsbiautomatic monoidshyperbolic monoidsword problem

Mathematics Subject Classification ID

Hyperbolic groups and nonpositively curved groups (20F67) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Review text

In this very interesting paper, the authors introduce a notion of hyperbolicity in monoids which provides an efficient, \(O(n\log n)\) time, algorithm for solving the word problem. This notion restricts one suggested in earlier work by Duncan and Gilman. Here, the resulting hyperbolic monoids are shown to be biautomatic.

Recommendations

• Notions of Hyperbolicity in Monoids
• Hyperaction of semigroups and monoids.
• Hyperbolicity of monoids presented by confluent monadic rewriting systems.
• Actions over monoids and hypergroups.
• scientific article; zbMATH DE number 2101007
• Hyperbolicity of semigroup algebras.
• Monoid hypersurfaces
• Geometric notes on monoids
• scientific article; zbMATH DE number 2201894

Cites work

• Automatic semigroups
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 1189057 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1254101 (Why is no real title available?)
• scientific article; zbMATH DE number 1944128 (Why is no real title available?)
• scientific article; zbMATH DE number 849252 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Notions of automaticity in semigroups.
• On the definition of word hyperbolic groups.
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• Visibly pushdown languages
• Word hyperbolic semigroups
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM

Cited in

(9)

• Decision problems for word-hyperbolic semigroups
• Hyperbolic groups and completely simple semigroups.
• Hyperbolicity of monoids presented by confluent monadic rewriting systems.
• scientific article; zbMATH DE number 1944128 (Why is no real title available?)
• How effects efficiency on the word problem for monoids?
• scientific article; zbMATH DE number 5225729 (Why is no real title available?)
• Notions of Hyperbolicity in Monoids
• MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS
• A strong geometric hyperbolicity property for directed graphs and monoids.

This page was built for publication: Notions of hyperbolicity in monoids.

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