Journal article

Publication year: 2021

Pages: 301-318

Journal: Acta Informatica

Volume number: 58

Issue number: 4

ISSN: 0001-5903

eISSN: 1432-0525

DOI Link: https://doi.org/10.1007/s00236-021-00397-8

Publisher: Springer

Abstract: 
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.

Harvard Citation style: Bordihn, H. and Holzer, M. (2021) On the number of active states in finite automata, Acta Informatica, 58(4), pp. 301-318. https://doi.org/10.1007/s00236-021-00397-8

APA Citation style: Bordihn, H., & Holzer, M. (2021). On the number of active states in finite automata. Acta Informatica. 58(4), 301-318. https://doi.org/10.1007/s00236-021-00397-8