Logical definability of Y-tree and trellis systolic ω-languages
In this paper we investigate the correspondence (in the style of the well known Büchi Theorem) between ω-languages accepted by systolic automata and suitable (proper) extensions of the Monadic Second Order theory of one successor (MSO[<]). To this purpose we extend Y-tree and trellis systolic aut...
Saved in:
| Main Authors: | |
|---|---|
| Format: | Article |
| Published: |
2001
|
| Series: | Acta cybernetica
15 No. 1 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12663 |
| Summary: | In this paper we investigate the correspondence (in the style of the well known Büchi Theorem) between ω-languages accepted by systolic automata and suitable (proper) extensions of the Monadic Second Order theory of one successor (MSO[<]). To this purpose we extend Y-tree and trellis systolic automata to deal with ω-words and we study the expressiveness, closure and decidability properties of the two classes of ω-languages accepted by Y-tree and trellis automata, respectively. We define, then, two extensions of MSO[<], MSO[<,adj] and MSO[<,2x], which allow to express Y-tree ω-languages and trellis ω-languages, respectively. |
|---|---|
| Physical Description: | 75-100 |
| ISSN: | 0324-721X |