The succinctness of first-order logic on linear orders
From MaRDI portal
Publication:5310637
DOI10.2168/LMCS-1(1:6)2005zbMath1125.03024OpenAlexW2950144551MaRDI QIDQ5310637
Martin Grohe, Nicole Schweikardt
Publication date: 11 October 2007
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2168/lmcs-1(1:6)2005
Logic in computer science (03B70) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)
Related Items (12)
Enumeration for FO Queries over Nowhere Dense Graphs ⋮ Expressive power and succinctness of the positive calculus of binary relations ⋮ On the Hybrid Extension of CTL and CTL + ⋮ On FO 2 Quantifier Alternation over Words ⋮ On the succinctness of some modal logics ⋮ Unnamed Item ⋮ The succinctness of the cover modality ⋮ Expressive Power and Succinctness of the Positive Calculus of Relations ⋮ On the complexity of existential positive queries ⋮ Comparing the succinctness of monadic query languages over finite trees ⋮ Logical Foundations of XML and XQuery ⋮ Model Checking FO(R) over One-Counter Processes and beyond
This page was built for publication: The succinctness of first-order logic on linear orders