Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

On the length of a transition tour of a finite automaton

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)

← Back to issue

× Issue cover