Logical definability of Y-tree and trellis systolic ω-languages

  • Monti Angelo
  • Adriano Peron


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.


Download data is not yet available.
How to Cite
Angelo, M., & Peron, A. (2001). Logical definability of Y-tree and trellis systolic ω-languages. Acta Cybernetica, 15(1), 75-100. Retrieved from https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3564
Regular articles