The characterization of the class of FO[+]-definable languages by some generat- ing or recognizing device is still an open problem. We prove that, restricted to word bounded languages, this class coincides with the class of semilinear languages. We also study the clo- sure properties of the classes of languages definable in FO[+1], FO[<], FO[+] and FOC[+] under the main classical operations.
First-order logics : some characterizations and closure properties / C. Choffrut, A. Malcher, C. Mereghetti, B.S. Palano. - In: ACTA INFORMATICA. - ISSN 0001-5903. - 49:4(2012 May), pp. 225-248.
First-order logics : some characterizations and closure properties
C. MereghettiPenultimo
;B.S. PalanoUltimo
2012
Abstract
The characterization of the class of FO[+]-definable languages by some generat- ing or recognizing device is still an open problem. We prove that, restricted to word bounded languages, this class coincides with the class of semilinear languages. We also study the clo- sure properties of the classes of languages definable in FO[+1], FO[<], FO[+] and FOC[+] under the main classical operations.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
978.5 kB
Formato
Adobe PDF
|
978.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.