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: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 208:4(2010 Apr), pp. 385-394. [10.1016/j.ic.2010.01.002]
More concise representation of regular languages by automata and regular expressions
C. MereghettiSecondo
;B.S. PalanoUltimo
2010
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
197.5 kB
Formato
Adobe PDF
|
197.5 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.
