A1 Refereed original research article in a scientific journal
Descriptional Complexity of Finite Automata-Selected Highlights
Authors: Salomaa, Arto; Salomaa, Kai; Smith, Taylor J.
Publisher: IOS Press BV
Publication year: 2024
Journal: Fundamenta Informaticae
Journal name in source: Fundamenta Informaticae
Volume: 191
Issue: 3-4
First page : 231
Last page: 237
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-242180
Web address : https://doi.org/10.3233/FI-242180
Self-archived copy’s web address: https://arxiv.org/pdf/2301.03708
Preprint address: https://arxiv.org/abs/2301.03708
Abstract
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.
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.
UTU Research Portal