Positive First-order Logic on Words and Graphs

DOI10.46298/lmcs-19(3:7)2023arXiv2201.11619MaRDI QIDQ6135776

Denis Kuperberg

Publication date: 26 August 2023

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

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

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Properties preserved under homomorphism
• Regular Cost Functions, Part I: Logic and Algebra over Words
• Green’s Relations and Their Use in Automata Theory
• On the Expressive Power of Cost Logics over Infinite Words
• Homomorphism preservation theorems
• Monotone versus positive
• Logical Description of Monotone NP Problems
• New results on the generalized star-height problem
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Magnitude Monadic Logic over Words and the Use of Relative Internal Set Theory
• Computer Science Logic
• On finite monoids having only trivial subgroups
• Linear Temporal Logic for Regular Cost Functions
• The undecidability of the Turing machine immortality problem

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