Infinitary logic for computer science

DOI10.1007/3-540-55719-9_96zbMath1427.03049OpenAlexW1510816031MaRDI QIDQ5204339

Phokion G. Kolaitis, Moshe Y. Vardi

Publication date: 4 December 2019

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

Full work available at URL: https://doi.org/10.1007/3-540-55719-9_96

zbMATH Keywords

extension axiomexpressive powerwinning strategyasymptotic probabilitypattern graph

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45) Logic in computer science (03B70) Model theory of finite structures (03C13) Other infinitary logic (03C75)

Related Items

Unification of infinite sets of terms schematized by primal grammars, Implicit definability and infinitary logic in finite model theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• The directed subgraph homeomorphism problem
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• An observation on time-storage trade off
• Elementary induction on abstract structures
• Datalog vs first-order logic
• Structure and complexity of relational queries
• Infinitary logic and inductive definability over finite structures
• Concerning measures in first order calculi
• Undecidable optimization problems for database logic programs
• Horn clause queries and generalizations
• A zero-one law for logic with a fixed-point operator
• Relational queries computable in polynomial time
• Second-order and Inductive Definability on Finite Structures
• Monadic generalized spectra
• Probabilities on finite models
• On Moschovakis closure ordinals
• Fixpoint logics, relational machines, and computational complexity