Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426660 | Information and Computation | 2010 | 10 Pages |
Abstract
We consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We constructively prove that their sizes are polynomially related. Comparing them with the sizes of finite state automata and regular expressions, we obtain optimal exponential and double exponential gaps, i.e., a more concise representation of regular languages.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics