A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

A new hierarchy for automaton semigroups




TekijätLaurent Bartholdi, Thibault Godin, Ines Klimann, Matthieu Picantin

ToimittajaCezar Câmpeanu

Konferenssin vakiintunut nimiInternational Conference on Implementation and Application of Automata (CIAA)

KustantajaSpringer Verlag

Julkaisuvuosi2018

JournalLecture Notes in Computer Science

Kokoomateoksen nimiImplementation and Application of Automata. 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 – August 2, 2018, Proceedings

Tietokannassa oleva lehden nimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Sarjan nimiLecture Notes in Computer Science

Vuosikerta10977

Aloitussivu71

Lopetussivu83

Sivujen määrä13

ISBN978-3-319-94811-9

eISBN978-3-319-94812-6

ISSN0302-9743

DOIhttps://doi.org/10.1007/978-3-319-94812-6_7


Tiivistelmä

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

The former results are implemented and will be available in the GAP package FR developed by the first author.



Last updated on 2024-26-11 at 19:24