The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable

Klaus Aehlig, Jolie G. de Miranda, C.-h. Luke Ong

Abstract

A tree automaton can simulate the successful runs of a word or tree automaton working on the word or tree denoted by a level-2 lambda-tree. In particular the monadic second order theory of trees given by arbitrary, rather than only by safe, recursion schemes of level 2 is decidable. This solves the level-2 case of an open problem by Knapik, Niwiński and Urzyczyn.
BibTeX
@inproceedings{aehlig2005monadic,
  author = {Klaus Aehlig and Jolie G. de Miranda and C.-H. Luke Ong},
  title = {{The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable}},
  booktitle = {TLCA},
  year = {2005},
  doi = {10.1007/11417170\_5},
}

Loading related content...

Figure