On the Size Complexity of Deterministic Frequency AutomataAuthors: Rūsiņš Freivalds, Thomas Zeugmann, and Grant R. Pogosyan
Source: Language and Automata Theory and Applications,
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!. The research was supported by Grant No. 09.1570 from the Latvian Council of Science and the Invitation Fellowship for Research in Japan S12052 by the Japan Society for the Promotion of Science ©Copyright 2013, Springer |