The characterization of the class of FO[ + ]-definable languages by some generating or recognizing device is still an open problem. We prove that, restricted to bounded languages, this class coincides with the class of semilinear languages. We also study some closure properties of FO[ + ]-definable languages which, as a by-product, allow us to give an alternative proof that the Dyck languages cannot be defined in FO[ + ].
On the expressive power of FO[+] / C. Choffrut, A. Malcher, C. Mereghetti, B.S. Palano (LECTURE NOTES IN COMPUTER SCIENCE). - In: Language and Automata Theory and Applications / [a cura di] A.-H. Dediu, H. Fernau, C. Martín-Vide. - Berlin : Springer, 2010. - ISBN 9783642130885. - pp. 190-201 (( Intervento presentato al 4. convegno Language and Automata Theory and Application tenutosi a Trier nel 2010 [10.1007/978-3-642-13089-2_16].
On the expressive power of FO[+]
C. MereghettiPenultimo
;B.S. PalanoUltimo
2010
Abstract
The characterization of the class of FO[ + ]-definable languages by some generating or recognizing device is still an open problem. We prove that, restricted to bounded languages, this class coincides with the class of semilinear languages. We also study some closure properties of FO[ + ]-definable languages which, as a by-product, allow us to give an alternative proof that the Dyck languages cannot be defined in FO[ + ].File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
223.81 kB
Formato
Adobe PDF
|
223.81 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.