Positive and monotone fragments of FO and LTL
<|reference_start|>Positive and monotone fragments of FO and LTL: We study the positive logic FO+ on finite words, and its fragments, pursuing and refining the work initiated in [Kuperberg 2023]. First, we transpose notorious logic equivalences into positive first-order logic: FO+ is equivalent to LTL+ , and its two-variable fragment FO2+ with (resp. without) successor available is equivalent to UTL+ with (resp. without) the "next" operator X available. This shows that despite previous negative results, the class of FO+-definable languages exhibits some form of robustness. We then exhibit an example of an FO-definable monotone language on one predicate, that is not FO+-definable, refining the example from [Kuperberg 2023] with 3 predicates. Moreover, we show that such a counter-example cannot be FO2-definable.<|reference_end|>
@article{kuperberg2024positive,
    title={Positive and monotone fragments of FO and LTL},
    author={Denis Kuperberg and Quentin Moreau},
    journal={arXiv preprint arXiv:2406.17693},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.17693},
    primaryClass={cs.LO cs.FL}
}