Positive First-order Logic on Words and Graphs

DOI10.46298/LMCS-19(3:7)2023MaRDI QIDQ6135776zbMATH OpenFDO

Authors Denis Kuperberg

Publication date 26 August 2023

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2201.11619

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

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 lift this example language to finite graphs, thereby providing a new result of independent interest for FO-definable graph classes: negation might be needed even when the class is closed under addition of edges. We finally show that the problem of whether a given regular language of finite words is definable in FO+ is undecidable.

Recommendations

• On first-order logic and CPDA graphs
• scientific article; zbMATH DE number 2143018
• First-Order Logic on CPDA Graphs
• Graph Transformations
• Conceptual Graphs and First Order Logic
• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• A note on strictly positive logics and word rewriting systems

Cites work

• Computer Science Logic
• Elements of finite model theory.
• First-order definable languages
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Green's relations and their use in automata theory
• Homomorphism preservation theorems
• scientific article; zbMATH DE number 176869 (Why is no real title available?)
• scientific article; zbMATH DE number 1086487 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Linear temporal logic for regular cost functions
• Logical Description of Monotone NP Problems
• Magnitude monadic logic over words and the use of relative internal set theory
• Monotone versus positive
• New results on the generalized star-height problem
• On finite monoids having only trivial subgroups
• On the Expressive Power of Cost Logics over Infinite Words
• Properties preserved under homomorphism
• Regular cost functions. I: Logic and algebra over words
• The undecidability of the Turing machine immortality problem

Cited in

(1)

• First-Order Logic on CPDA Graphs

This page was built for publication: Positive First-order Logic on Words and Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135776)