Implicit definability and infinitary logic in finite model theory

DOI10.1007/3-540-60084-1_110zbMath1415.03041OpenAlexW2134463605WikidataQ58215765 ScholiaQ58215765MaRDI QIDQ4645216

Lauri Hella, Phokion G. Kolaitis, Anuj Dawar

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60084-1_110

zbMATH Keywords

expressive powerlinear orderrelational queryimplicit definitionrelation symbol

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Interpolation, preservation, definability (03C40) Other infinitary logic (03C75) Descriptive complexity and finite models (68Q19)

Related Items

How to define a linear order on finite models, Recursive definitions and fixed-points on well-founded structures, Recursive Definitions and Fixed-Points

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper and lower bounds for first order expressibility
• An analysis of fixed-point queries on binary trees
• Model theory.
• Infinitary logics and 0-1 laws
• Relative complexity of checking and evaluating
• Structure and complexity of relational queries
• Infinitary logic and inductive definability over finite structures
• Relational queries computable in polynomial time
• On Moschovakis closure ordinals
• Fixpoint logics, relational machines, and computational complexity
• On finite rigid structures
• Infinitary logic for computer science