TY - CHAP
T1 - On the determinization blowup for finite automata recognizing equal-length languages
AU - Karhumäki, Juhani
AU - Okhotin, Alexander
PY - 2014/1/1
Y1 - 2014/1/1
N2 - Motivated by the application to image compression (K. Čulìk II, J. Kari, “Image compression using weighted finite automata”, Computers & Graphics, 1993), the paper considers finite automata representing formal languages with all strings of the same length, and investigates relative succinctness of representation by deterministic and nondeterministic finite automata (DFA, NFA). It is shown that an n-state NFA recognizing a language of strings of length _ over a k-symbol alphabet can be transformed to a DFA with at most _ · k_ 2 log2 k n+3_+3 = 2O(√n) states. At the same time, for every k-symbol alphabet with k _ 2, and for every n _ 1, there exists an n-state NFA recognizing an equal-length language, which requires a DFA with at least k√ n k−1−2 = 2Ω(√n) states.
AB - Motivated by the application to image compression (K. Čulìk II, J. Kari, “Image compression using weighted finite automata”, Computers & Graphics, 1993), the paper considers finite automata representing formal languages with all strings of the same length, and investigates relative succinctness of representation by deterministic and nondeterministic finite automata (DFA, NFA). It is shown that an n-state NFA recognizing a language of strings of length _ over a k-symbol alphabet can be transformed to a DFA with at most _ · k_ 2 log2 k n+3_+3 = 2O(√n) states. At the same time, for every k-symbol alphabet with k _ 2, and for every n _ 1, there exists an n-state NFA recognizing an equal-length language, which requires a DFA with at least k√ n k−1−2 = 2Ω(√n) states.
UR - http://www.scopus.com/inward/record.url?scp=84916894231&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-13350-8_6
DO - 10.1007/978-3-319-13350-8_6
M3 - Chapter
AN - SCOPUS:84916894231
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 71
EP - 82
BT - Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday
ER -