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

Juhani Karhumäki; Alexander Okhotin

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

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

Juhani Karhumäki, Alexander Okhotin

Факультет математико-механический

Research output

Abstract

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.

Original language	English
Title of host publication	Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday
Pages	71-82
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-319-13350-8_6
Publication status	Published - 1 Jan 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	8808
ISSN (Print)	0302-9743

Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

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

http://www.scopus.com/inward/record.url?scp=84916894231&partnerID=8YFLogxK

Fingerprint Dive into the research topics of 'On the determinization blowup for finite automata recognizing equal-length languages'. Together they form a unique fingerprint.

Cite this

Karhumäki, J., & Okhotin, A. (2014). On the determinization blowup for finite automata recognizing equal-length languages. In Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday (pp. 71-82). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8808). https://doi.org/10.1007/978-3-319-13350-8_6

Karhumäki, Juhani ; Okhotin, Alexander. / On the determinization blowup for finite automata recognizing equal-length languages. Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday. 2014. pp. 71-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{601a734f8735496a9c565c8575046d82,

title = "On the determinization blowup for finite automata recognizing equal-length languages",

abstract = "Motivated by the application to image compression (K. {\v C}ul{\`i}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.",

author = "Juhani Karhum{\"a}ki and Alexander Okhotin",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-13350-8_6",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "71--82",

booktitle = "Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday",

}

Karhumäki, J & Okhotin, A 2014, On the determinization blowup for finite automata recognizing equal-length languages. in Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8808, pp. 71-82. https://doi.org/10.1007/978-3-319-13350-8_6

On the determinization blowup for finite automata recognizing equal-length languages. / Karhumäki, Juhani; Okhotin, Alexander.

Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday. 2014. p. 71-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8808).

Research output

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 -

Karhumäki J, Okhotin A. On the determinization blowup for finite automata recognizing equal-length languages. In Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday. 2014. p. 71-82. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-13350-8_6