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. Mereghetti
Penultimo
;
B.S. Palano
Ultimo
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[ + ].
Bounded languages; semilinear sets; first order logic
Settore INF/01 - Informatica
2010
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/140074
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact