TY  - JOUR
A1  - Gramlich, Gregor
A2  - Rovan, Branislav
A2  - Vojtáš, Peter
T1  - Probabilistic and nondeterministic unary automata
N2  - We investigate unary regular languages and compare deterministic finite automata (DFA’s), nondeterministic finite automata (NFA’s) and probabilistic finite automata (PFA’s) with respect to their size. Given a unary PFA with n states and an e-isolated cutpoint, we show that the minimal equivalent DFA has at most n exp 1/2e states in its cycle. This result is almost optimal, since for any alpha < 1 a family of PFA’s can be constructed such that every equivalent DFA has at least n exp alpha/2e states. Thus we show that for the model of probabilistic automata with a constant error bound, there is only a polynomial blowup for cyclic languages. Given a unary NFA with n states, we show that efficiently approximating the size of a minimal equivalent NFA within the factor sqrt(n)/ln n is impossible unless P = NP. This result even holds under the promise that the accepted language is cyclic. On the other hand we show that we can approximate a minimal NFA within the factor ln n, if we are given a cyclic unary n-state DFA.
KW  - Theoretische Informatik
KW  - Kongress
KW  - Preßburg <2003>
KW  - Online-Publikation
Y1  - 2003
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/864
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-44876
SN  - 978-3-540-45138-9
SN  - 978-3-540-40671-6
SN  - 3-540-40671-9
N1  - Die Arbeit erhielt den "Best student paper award".
N1  - Überarbeitete Fassung von: Branislav Rovan ; Peter Vojtáš (Hrsg.): Mathematical foundations of computer science 2003 : 28th international symposium ; proceedings, Berlin ; Heidelberg ; New York ; Hong Kong ; London ; Milan ; Paris ; Tokyo : Springer, 2003, Lecture notes in computer science ; Vol. 2747, S. 460–469, ISBN: 978-3-540-40671-6, ISBN: 3-540-40671-9, ISBN: 978-3-540-45138-9, doi:10.1007/b11836
ER  -