On the Size Complexity of Deterministic Frequency Automata

Authors: Rūsiņš Freivalds, Thomas Zeugmann, and Grant R. Pogosyan

Source: Language and Automata Theory and Applications,
7th International Conference, LATA 2013, Bilbao, Spain, April 2-5, 2013, Proceedings
(Adrian-Horia Dediu, Carlos Martín-Vide, and Bianca Truthe, Eds.) Lecture Notes in Computer Science 7810, pp. 287-298, Springer 2012.

Abstract. Austinat, Diekert, Hertrampf, and Petersen (2005) proved that every language L that is (m,n)-recognizable by a deterministic frequency automaton such that m > n/2 can be recognized by a deterministic finite automaton as well. First, the size of deterministic frequency automata and of deterministic finite automata recognizing the same language is compared. Then approximations of a language are considered, where a language L' is called an approximation of a language L if L' differs from L in only a finite number of strings. We prove that if a deterministic frequency automaton has k states and (m,n)-recognizes a language L, where m > n/2, then there is a language L' approximating L such that L' can be recognized by a deterministic finite automaton with no more than k states.

Austinat et al. (2005) also proved that every language L over a single-letter alphabet that is (1,n)-recognizable by a deterministic frequency automaton can be recognized by a deterministic finite automaton. For languages over a single-letter alphabet we show that if a deterministic frequency automaton has k states and (1,n)-recognizes a language L then there is a language L' approximating L such that L' can be recognized by a deterministic finite automaton with no more that k states. However, there are approximations such that our bound is much higher, i.e., k!.