On a Fragment of AMSO and Tiling Systems

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
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:

You are running an old browser version. We recommend updating your browser to its latest version.