In the realm of descriptional complexity, systems are compared on the basis of their size. Here, we consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We show 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.
Descriptional Complexity Issues Concerning Regular Languages / V. Geffert, C. Mereghetti, B.S. Palano - In: Theorietag Automaten und Formale Sprachen / [a cura di] M. Holzer, M. Kutrib, A. Malcher. - Giessen : Universitat Giessen, 2008. - ISBN 9783000259203. - pp. 11-22 (( Intervento presentato al 18. convegno Automaten und Formale Sprachen tenutosi a Giessen nel 2008.
Descriptional Complexity Issues Concerning Regular Languages
C. MereghettiSecondo
;B.S. PalanoUltimo
2008
Abstract
In the realm of descriptional complexity, systems are compared on the basis of their size. Here, we consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We show 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 | |
|---|---|---|---|
|
tafs08.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
202.24 kB
Formato
Adobe PDF
|
202.24 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.
