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. Mereghetti
Penultimo
;
B.S. Palano
Ultimo
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.
Bounded languages; Semilinear sets; First order logic
Settore INF/01 - Informatica
mag-2012
Article (author)
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.

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