Quasi-automatic semigroups
| Autor: | Christophe Reutenauer, Christian Choffrut, Benjamin Blanchette |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Pure mathematics General Computer Science Semigroup Formal Languages and Automata Theory (cs.FL) Computer Science - Formal Languages and Automata Theory Group Theory (math.GR) Computational Complexity (cs.CC) Lipschitz continuity Theoretical Computer Science Exponential function Decidability Computer Science - Computational Complexity FOS: Mathematics Mathematics - Combinatorics Rational relation Word problem (mathematics) Combinatorics (math.CO) Isoperimetric inequality Finite set Mathematics - Group Theory Mathematics |
| DOI: | 10.48550/arxiv.1906.02842 |
| Popis: | A quasi-automatic semigroup is defined by a finite set of generators, a rational (regular) set of representatives, such that if a is a generator or neutral, then the graph of right multiplication by a on the set of representatives is a rational relation. This class of semigroups contains previously considered semigroups and groups (Sakarovitch, Epstein et al., Campbell et al.). Membership of a semigroup to this class does not depend on the choice of the generators. These semigroups are rationally presented. Representatives may be computed in exponential time. Their word problem is decidable in exponential time. They enjoy a property similar to the so-called Lipschitz property, or fellow traveler property. If graded, they are automatic. In the case of groups, they are finitely presented with an exponential isoperimetric inequality and they are characterized by the weak Lipschitz property. Comment: 17 pages. In press. Theoretical Computer Science, 2019 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|