Positive First-order Logic on Words
Denis Kuperberg
2021Year
3Citations
1Top-tier citations
Abstract
We study FO + , a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is an FO-definable language that is monotone in monadic predicates but not definable in FO + . This provides a simple proof that Lyndon's preservation theorem fails on finite structures. We additionally show that given a regular language, it is undecidable whether it is definable in FO + .
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Cited by top-tier papers1
Ask how each one uses itRelated papers
- Extensions of ω-Regular LanguagesMikolaj Bojanczyk, Edon Kelmendi, Rafal Stefanski, Georg ZetzscheLICS 2020
- First-Order AutomataLuca Geatti, Alessandro Gianola, Nicola GiganteAAAI 2025 · 3 citations
- Successor-Invariant First-Order Logic on Classes of Bounded DegreeJulien GrangeLICS 2020 · 1 citation
- Characterization and Decidability of FC-Definable Regular LanguagesSam M. Thompson, Nicole Schweikardt, Dominik D. FreydenbergerLICS 2025
- Uniformisation of Regular Relations in First-Order Logic with Two VariablesNathan Lhote, Vincent Michielini, Michal SkrzypczakLICS 2024
