The succinctness of first-order logic on linear orders

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

Mathematics Subject Classification ID

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