Two-Variable Logic with Two Order Relations

DOI10.2168/LMCS-8(1:15)2012zbMath1238.03031arXiv1110.1439MaRDI QIDQ5891508

Thomas Schwentick, Thomas Zeume

Publication date: 3 April 2012

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

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

zbMATH Keywords

linear orderstwo-variable logicdata word

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Unnamed Item, Two-Variable Separation Logic and Its Inner Circle, Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable, Church synthesis on register automata over linearly ordered data domains, Synthesis of Data Word Transducers, Unnamed Item