004 Datenverarbeitung; Informatik
Refine
Has Fulltext
- no (214) (remove)
Year of publication
Document Type
- Article (162)
- Doctoral Thesis (24)
- Conference Proceeding (16)
- Other (7)
- Monograph/Edited Volume (3)
- Part of a Book (2)
Is part of the Bibliography
- yes (214)
Keywords
- social media (4)
- Data profiling (3)
- evaluation (3)
- machine learning (3)
- Blockchains (2)
- Deep learning (2)
- General Earth and Planetary Sciences (2)
- Geography, Planning and Development (2)
- JSP (2)
- Machine Learning (2)
Institute
- Institut für Informatik und Computational Science (64)
- Hasso-Plattner-Institut für Digital Engineering gGmbH (46)
- Fachgruppe Betriebswirtschaftslehre (28)
- Hasso-Plattner-Institut für Digital Engineering GmbH (27)
- Bürgerliches Recht (12)
- Wirtschaftswissenschaften (11)
- Institut für Mathematik (6)
- Institut für Biochemie und Biologie (4)
- Institut für Physik und Astronomie (4)
- Department Erziehungswissenschaft (3)
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.