Publication details

On a Fragment of AMSO and Tiling Systems

Authors

BLUMENSATH Achim COLCOMBET Thomas PARYS Pawel

Type Article in Proceedings
Conference 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orleans, France
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.4230/LIPIcs.STACS.2016.19
Field Informatics
Keywords monadic second-order logic; boundedness; tiling problems
Description We prove that satisfiability over infinite words is decidable for a fragment of asymptotic monadic second-order logic. In this fragment we only allow formulae of the form \exists t\forall s\exists r\phi(r,s,t), where \phi does not use quantifiers over number variables, and variables r and s can be only used simultaneously, in subformulae of the form s < f(x) <= r.
Related projects: