Finite transducers for divisibility monoids
From MaRDI portal
Publication:2508976
Abstract: Divisibility monoids are a natural lattice-theoretical generalization of Mazurkiewicz trace monoids, namely monoids in which the distributivity of the involved divisibility lattices is kept as an hypothesis, but the relations between the generators are not supposed to necessarily be commutations. Here, we show that every divisibility monoid admits an explicit finite transducer which allows to compute normal forms in quadratic time. In addition, we prove that every divisibility monoid is biautomatic.
Recommendations
Cites work
- A Geometric Characterization of Automatic Monoids
- Automatic groups and amalgams
- Automatic semigroups
- Automatic Structures for Torus Link Groups
- Combinatorial problems of commutation and rearrangements
- Computing the average parallelism in trace monoids.
- Easy multiplications. I: The realm of Kleene's theorem
- Garside monoids vs divisibility monoids
- Groupes de Garside
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (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 1740168 (Why is no real title available?)
- scientific article; zbMATH DE number 1839447 (Why is no real title available?)
- scientific article; zbMATH DE number 3245483 (Why is no real title available?)
- Non-positively curved aspects of Artin groups of finite type
- Notions of automaticity in semigroups.
- On the base-dependence of sets of numbers recognizable by finite automata
- Recognizable languages in concurrency monoids
- Recognizable languages in divisibility monoids
- The On-Line Encyclopedia of Integer Sequences
Cited in
(11)- Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\)
- Cyclic amalgams, HNN extensions, and Garside one-relator groups
- Automaticity of one-relator semigroups with length less than or equal to three
- Garside monoids vs divisibility monoids
- scientific article; zbMATH DE number 4116825 (Why is no real title available?)
- scientific article; zbMATH DE number 1839447 (Why is no real title available?)
- Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids.
- scientific article; zbMATH DE number 1390068 (Why is no real title available?)
- Automatic semigroups vs automaton semigroups
- Implementation and Application of Automata
- Over Which Monoids is the Transducer Determinization Procedure Applicable?
This page was built for publication: Finite transducers for divisibility monoids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2508976)
