On the length of a transition tour of a finite automaton
Received: 05 Oct 2026 Accepted: 24 Oct 2026
Published: 2026, vol. 30, issue 4, pp. 103–106
Abstract
We consider closed transition tours of a complete finite deterministic automaton with a fixed initial state. We state a known sharp general bound and describe a family of automata attaining it. We give a criterion for the minimum tour length to equal the number of transitions and show that this equality holds for strongly connected permutation automata and linear automata over a finite field.
Keywords: finite automaton, transition tour, linear automaton, Eulerian circuit.
BibTeX
@article{IS-Kunitsyn2026,
author = {Kunitsyn, Aleksandr Aleksandrovich},
title = {{On the length of a transition tour of a finite automaton}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {103--106},
}
AMSBIB
\Bibitem{IS-Kunitsyn2026}
\by A.\,A.~Kunitsyn
\paper On the length of a transition tour of a finite automaton
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 103--106
\lang In Russian
Published under
Creative Commons Attribution 4.0 International (CC BY 4.0)
RU