𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s

✍ Scribed by Juraj Hromkovič; Holger Petersen; Georg Schnitger

Book ID
108281538
Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
761 KB
Volume
410
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A lower bound on the size of ε-free NFA
A lower bound on the size of ε-free NFA corresponding to a regular expression
✍ Yuri Lifshits 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 110 KB

Hromkovic et al. showed how to transform a regular expression of size n into an ε-free nondeterministic finite automaton (which defines the same language as the expression) with O(n) states and O(n log 2 (n)) transitions. They also established a lower bound (n log(n)) on the number of transitions. W