The succinctness of first-order logic on linear orders
From MaRDI portal
Publication:5310637
DOI10.2168/LMCS-1(1:6)2005zbMath1125.03024MaRDI 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
03B70: Logic in computer science
03C13: Model theory of finite structures
68Q19: Descriptive complexity and finite models
Related Items
The succinctness of the cover modality, Comparing the succinctness of monadic query languages over finite trees, Unnamed Item, Expressive Power and Succinctness of the Positive Calculus of Relations, On the complexity of existential positive queries, Enumeration for FO Queries over Nowhere Dense Graphs, On the succinctness of some modal logics, 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, Logical Foundations of XML and XQuery, Model Checking FO(R) over One-Counter Processes and beyond