The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Buchi's approach, we introduce a variant of monadic second-order logic with data equality tests that captures precisely the data languages recognizable by orbit finite data monoids. We also establish, following this time the approach of Schutzenberger, McNaughton and Papert, that the first-order fragment of this logic defines exactly the data languages recognizable by aperiodic orbit finite data monoids. Finally, we consider another variant of the logic that can be interpreted over generic structures with data. The data languages defined in this variant are also recognized by unambiguous finite memory automata.

Logics with rigidly guarded data tests

Puppis G.
2015-01-01

Abstract

The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Buchi's approach, we introduce a variant of monadic second-order logic with data equality tests that captures precisely the data languages recognizable by orbit finite data monoids. We also establish, following this time the approach of Schutzenberger, McNaughton and Papert, that the first-order fragment of this logic defines exactly the data languages recognizable by aperiodic orbit finite data monoids. Finally, we consider another variant of the logic that can be interpreted over generic structures with data. The data languages defined in this variant are also recognized by unambiguous finite memory automata.
File in questo prodotto:
File Dimensione Formato  
LMCS 2015a Editoriale.pdf

accesso aperto

Descrizione: LMCS 2015a versione editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 579.06 kB
Formato Adobe PDF
579.06 kB Adobe PDF Visualizza/Apri
LMCS 2015a Postprint.pdf

accesso aperto

Descrizione: LMCS 2015a versione post-print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 600.52 kB
Formato Adobe PDF
600.52 kB Adobe PDF Visualizza/Apri

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/11390/1174094
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 4
social impact