On a Fragment of AMSO and Tiling Systems
| Autoři | |
|---|---|
| Rok publikování | 2016 |
| Druh | Článek ve sborníku |
| Konference | 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orleans, France |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2016.19 |
| Obor | Informatika |
| Klíčová slova | monadic second-order logic; boundedness; tiling problems |
| Přiložené soubory | |
| Popis | 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. |
| Související projekty: |