• search hit 24 of 1097
Back to Result List

On the number of active states in finite automata

  • 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.

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:Henning BordihnORCiD, Markus HolzerORCiDGND
DOI:https://doi.org/10.1007/s00236-021-00397-8
ISSN:0001-5903
ISSN:1432-0525
Title of parent work (English):Acta informatica
Publisher:Springer
Place of publishing:Berlin ; Heidelberg [u.a.]
Publication type:Article
Language:English
Date of first publication:2021/08/14
Publication year:2021
Release date:2023/09/27
Volume:58
Issue:4
Number of pages:18
First page:301
Last Page:318
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
DDC classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Peer review:Referiert
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.