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.
More concise representation of regular languages by automata and regular expressions / V. Geffert, C. Mereghetti, B. S. Palano - In: Developments in Language Theory / [a cura di] M. Ito, M. Toyama. - Berlin : Springer, 2008. - ISBN 9783540857792. - pp. 359-370 (( Intervento presentato al 12. convegno Developments in Language Theory tenutosi a Kyoto nel 2008.
More concise representation of regular languages by automata and regular expressions
C. MereghettiSecondo
;B. S. PalanoUltimo
2008
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
493.78 kB
Formato
Adobe PDF
|
493.78 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
