A Short Note on Two-Variable Logic with a Linear Order Successor and a Preorder Successor

2013/06/14 by Amaldev Manuel, Manuel, Amaldev, Thomas Schwentick +3
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.48550/arxiv.1306.3418

openalex publication_date 2013/06/14 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

The finite satisfiability problem of two-variable logic extended by a linear order successor and a preorder successor is shown to be undecidable.

Related

• Satisfiability for two-variable logic with two successor relations on finite linear orders
• Order-Invariance of Two-Variable Logic is Decidable
• Order-Invariance in the Two-Variable Fragment of First-Order Logic
• Order-Invariance of Two-Variable Logic is coNExpTime-complete
• Two-Variable Logic for Hierarchically Partitioned and Ordered Data