2026-07-23T00:23:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6578 2024-03-06T10:38:45Z ddc:004 open_access

One-Dimensional Logic over Words Kieronski, Emanuel satisfiability expressivity words fragments of first-order logic One-dimensional fragment of first-order logic is obtained by restricting quantification to blocks of existential quantifiers that leave at most one variable free. We investigate one-dimensional fragment over words and over omega-words. We show that it is expressively equivalent to the two-variable fragment of first-order logic. We also show that its satisfiability problem is NExpTime-complete. Further, we show undecidability of some extensions, whose two-variable counterparts remain decidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emanuel Kieronski 2016 Is Part Of LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2016.38 urn:nbn:de:0030-drops-65782 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.38 eng https://creativecommons.org/licenses/by/3.0/legalcode