On the determinization blowup for finite automata recognizing equal-length languages

被引：3

作者：

机构：

[1] Department of Mathematics and Statistics, University of Turku, Turku

来源：

Karhumäki, Juhani | 1600年 / Springer Verlag卷 / 8808期

基金：

芬兰科学院;

关键词：

Image compression - Formal languages - Pipeline processing systems;

D O I：

10.1007/978-3-319-13350-8_6

中图分类号：

学科分类号：

摘要：

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. © Springer International Publishing Switzerland 2014.

引用

页码：71 / 82

页数：11