Arto Salomaa ; Kai Salomaa ; Taylor J. Smith - Descriptional Complexity of Finite Automata -- Selected Highlights

fi:10876 - Fundamenta Informaticae, November 10, 2024, Volume 191, Issues 3-4: Iiro Honkala's 60 Birthday
Descriptional Complexity of Finite Automata -- Selected HighlightsArticle

Authors: Arto Salomaa ; Kai Salomaa ; Taylor J. Smith

    The state complexity, respectively, nondeterministic state complexity of a regular language $L$ is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for $L$. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.


    Volume: Volume 191, Issues 3-4: Iiro Honkala's 60 Birthday
    Published on: November 10, 2024
    Accepted on: September 28, 2023
    Submitted on: January 30, 2023
    Keywords: Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 8 times.
    This article's PDF has been downloaded 9 times.