TY  - JOUR
A1  - Bordihn, Henning
A1  - Holzer, Markus
T1  - On the number of active states in finite automata
T2  - Acta informatica
N2  - We introduce a new measure of descriptional complexity on finite automata, called the number of active states. Roughly speaking, the number of active states of an automaton A on input w counts the number of different states visited during the most economic computation of the automaton A for the word w. This concept generalizes to finite automata and regular languages in a straightforward way. We show that the number of active states of both finite automata and regular languages is computable, even with respect to nondeterministic finite automata. We further compare the number of active states to related measures for regular languages. In particular, we show incomparability to the radius of regular languages and that the difference between the number of active states and the total number of states needed in finite automata for a regular language can be of exponential order.
Y1  - 2021
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/60728
SN  - 0001-5903
SN  - 1432-0525
VL  - 58
IS  - 4
SP  - 301
EP  - 318
PB  - Springer
CY  - Berlin ; Heidelberg [u.a.]
ER  -