On a Fragment of AMSO and Tiling Systems
| Authors | |
|---|---|
| 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 | |
| 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: |