Back to Search
Start Over
A New Hierarchy for Automaton Semigroups.
- Source :
-
International Journal of Foundations of Computer Science . Dec2020, Vol. 31 Issue 8, p1069-1089. 21p. - Publication Year :
- 2020
-
Abstract
- We define a new strict and computable hierarchy for the family of automaton semigroups, which reflects the various asymptotic behaviors of the state-activity growth. This hierarchy extends that given by Sidki for automaton groups, and also gives new insights into the latter. Its exponential part coincides with a notion of entropy for some associated automata. We prove that the Order Problem is decidable whenever the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. Gillibert showed that it is undecidable in the whole family. We extend the aforementioned hierarchy via a semi-norm making it more coarse but somehow more robust and we prove that the Order Problem is still decidable for the first two levels of this alternative hierarchy. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ROBOTS
*HIERARCHIES
*STATISTICAL decision making
Subjects
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 31
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 148201684
- Full Text :
- https://doi.org/10.1142/S0129054120420046