This paper addresses a decision problem highlighted by Grigorchuk,
Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton
(semi)groups.
For semigroups, we give an effective sufficient but not necessary condition
for finiteness and, for groups, an effective necessary but not sufficient
condition. The efficiency of the new criteria is demonstrated by testing all
Mealy automata with small stateset and alphabet. Finally, for groups, we
provide a necessary and sufficient condition that does not directly lead to a
decision procedure.
Description
[1105.4725] On the Finiteness Problem for Automaton (Semi)groups
%0 Generic
%1 akhavi2011finiteness
%A Akhavi, Ali
%A Klimann, Ines
%A Lombardy, Sylvain
%A Mairesse, Jean
%A Picantin, Matthieu
%D 2011
%K automata semigroup
%R 10.1142/S021819671250052X
%T On the Finiteness Problem for Automaton (Semi)groups
%U http://arxiv.org/abs/1105.4725
%X This paper addresses a decision problem highlighted by Grigorchuk,
Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton
(semi)groups.
For semigroups, we give an effective sufficient but not necessary condition
for finiteness and, for groups, an effective necessary but not sufficient
condition. The efficiency of the new criteria is demonstrated by testing all
Mealy automata with small stateset and alphabet. Finally, for groups, we
provide a necessary and sufficient condition that does not directly lead to a
decision procedure.
@misc{akhavi2011finiteness,
abstract = {This paper addresses a decision problem highlighted by Grigorchuk,
Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton
(semi)groups.
For semigroups, we give an effective sufficient but not necessary condition
for finiteness and, for groups, an effective necessary but not sufficient
condition. The efficiency of the new criteria is demonstrated by testing all
Mealy automata with small stateset and alphabet. Finally, for groups, we
provide a necessary and sufficient condition that does not directly lead to a
decision procedure.},
added-at = {2015-01-06T04:11:03.000+0100},
author = {Akhavi, Ali and Klimann, Ines and Lombardy, Sylvain and Mairesse, Jean and Picantin, Matthieu},
biburl = {https://www.bibsonomy.org/bibtex/2c5b6377040ec548090f37fe637a0db52/t.uemura},
description = {[1105.4725] On the Finiteness Problem for Automaton (Semi)groups},
doi = {10.1142/S021819671250052X},
interhash = {02ec980c4d3fb55b64b41ac4a67868b7},
intrahash = {c5b6377040ec548090f37fe637a0db52},
keywords = {automata semigroup},
note = {cite \href{http://arxiv.org/abs/1105.4725}{arxiv:1105.4725}},
timestamp = {2015-01-06T04:11:03.000+0100},
title = {On the Finiteness Problem for Automaton (Semi)groups},
url = {http://arxiv.org/abs/1105.4725},
year = 2011
}