文章基本信息

标题：On a Fragment of AMSO and Tiling Systems
本地全文：下载
作者：Achim Blumensath ; Thomas Colcombet ; Pawel Parys 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：47
页码：19:1-19:14
DOI：10.4230/LIPIcs.STACS.2016.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：monadic second-order logic; boundedness; tiling problems