Paper Info
Title
A Logical Characterization of Systolic Languages
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′].
Year
DOI
Venue
1998
10.1007/BFb0028582
STACS
Keywords
Field
DocType
systolic languages,logical characterization,binary tree,regular language,first order
Discrete mathematics,Combinatorics,Formal language,Logic in computer science,Abstract family of languages,Decidability,Finite-state machine,Tree automaton,Regular language,Mathematics,Mathematical logic
Conference
Volume
ISSN
ISBN
1373
0302-9743
3-540-64230-7
Citations 
PageRank 
References 
1
0.44
7
Authors
2
Name
Order
Citations
PageRank
Angelo Monti167146.93
Adriano Peron238145.82