Quantifier alternation in first-order formulas with infinite spectra

DOI10.1134/S003294601704007XMaRDI QIDQ2190893zbMATH OpenOpenAlexFDO

Authors M. E. Zhukovskii

Publication date 23 June 2020

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s003294601704007x

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations
• First order sentences about random graphs: small number of alternations
• Infinite spectra of first-order properties for random hypergraphs
• On the spectra of first-order language properties for random graphs
• On the 4-spectrum of first-order properties of random graphs

Cites work

• Estimation of the number of maximal extensions in a random graph
• First-order and monadic properties of highly sparse random graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4041966 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Infinite spectra in the first order theory of graphs
• On infinite spectra of first-order properties of random graphs
• On the zero-one k-law extensions
• Probabilities on finite models
• Random graphs.
• Random graphs: models and asymptotic characteristics
• The probabilistic method
• The strange logic of random graphs
• Threshold functions for extension statements
• Threshold functions for small subgraphs
• Zero-one \(k\)-law
• Zero-One Laws for Sparse Random Graphs

Cited in

(8)

• First order sentences about random graphs: small number of alternations
• On the 4-spectrum of first-order properties of random graphs
• Infinite spectra of first-order properties for random hypergraphs
• Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words

This page was built for publication: Quantifier alternation in first-order formulas with infinite spectra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2190893)