We consider the satisfiability problem for the two-variable fragment of first-order logic extended with counting quantifiers, interpreted over finite words with data, denoted here with C²[≤ , succ, ∼, π_bin]. In our scenario, we allow for using arbitrary many uninterpreted binary predicates from π_bin, two navigational predicates ≤ and succ over word positions as well as a data-equality predicate ∼. We prove that the obtained logic is undecidable, which contrasts with the decidability of the logic without counting by Montanari, Pazzaglia and Sala [Angelo Montanari et al., 2016]. We supplement our results with decidability for several sub-fragments of C²[≤ , succ, ∼, π_bin], e.g. without binary predicates, without successor succ, or under the assumption that the total number of positions carrying the same data value in a data-word is bounded by an a priori given constant.
@InProceedings{bednarczyk_et_al:LIPIcs.TIME.2020.17, author = {Bednarczyk, Bartosz and Witkowski, Piotr}, title = {{A Note on C² Interpreted over Finite Data-Words}}, booktitle = {27th International Symposium on Temporal Representation and Reasoning (TIME 2020)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-167-2}, ISSN = {1868-8969}, year = {2020}, volume = {178}, editor = {Mu\~{n}oz-Velasco, Emilio and Ozaki, Ana and Theobald, Martin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2020.17}, URN = {urn:nbn:de:0030-drops-129850}, doi = {10.4230/LIPIcs.TIME.2020.17}, annote = {Keywords: Two-variable logic, data-words, VASS, decidability, undecidability, counting} }
Feedback for Dagstuhl Publishing