Positive first-order logic on words

2021/01/06 by Kuperberg, Denis
#F.4.1 #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2101.01968

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 a 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+.

Related

• Positive and monotone fragments of FO and LTL
• First-Order logic and its Infinitary Quantifier Extensions over Countable Words
• Languages of Dot-depth One over Infinite Words
• Fragments of first-order logic over infinite words
• Finite-Degree Predicates and Two-Variable First-Order Logic