The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable
Lists
Only you see this
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...