Publication details

On a Fragment of AMSO and Tiling Systems

Authors

BLUMENSATH Achim COLCOMBET Thomas PARYS Pawel

Year of publication 2016
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
Attached files
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: