In this paper we study, in the framework of mathematical logic, ℒ(SBTA) i.e. the class of languages accepted by Systolic Binary Tree Automata. We set a correspondence (in the style of Büchi Theorem for regular languages) between ℒ(SBTA) and MSO[Sig], i.e. a decidable Monadic Second Order logic over a suitable infinite signature Sig. We also introduce a natural subclass of ℒ(SBTA) which still properly contains the class of regular languages and which is proved to be characterized by Monadic Second Order logic over a finite signature Sig' ⊂ Sig. Finally, in the style of McNaughton Theorem for star free regular languages, we introduce an expression language which precisely denotes the class of languages defined by the first order fragment of MSO[Sig'].

A logical characterization of systolic languages

PERON, ADRIANO
1998

Abstract

In this paper we study, in the framework of mathematical logic, ℒ(SBTA) i.e. the class of languages accepted by Systolic Binary Tree Automata. We set a correspondence (in the style of Büchi Theorem for regular languages) between ℒ(SBTA) and MSO[Sig], i.e. a decidable Monadic Second Order logic over a suitable infinite signature Sig. We also introduce a natural subclass of ℒ(SBTA) which still properly contains the class of regular languages and which is proved to be characterized by Monadic Second Order logic over a finite signature Sig' ⊂ Sig. Finally, in the style of McNaughton Theorem for star free regular languages, we introduce an expression language which precisely denotes the class of languages defined by the first order fragment of MSO[Sig'].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11588/471032
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact