On asymptotic probabilities in logics that capture DSPACE( n) in presence of ordering

DOI10.1007/3-540-56610-4_90MaRDI QIDQ5044764zbMATH OpenOpenAlexFDO

Authors Jerzy Tyszkiewicz

Publication date 2 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-56610-4_90

Mathematics Subject Classification ID

Zero-one laws (60F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Infinitary logics and 0-1 laws
• Asymptotic conditional probabilities: The non-unary case
• The computational complexity of asymptotic problems. I: Partial orders
• A zero-one law for logic with a fixed-point operator
• Strong 0-1 laws in finite model theory

Cites work

• scientific article; zbMATH DE number 58300 (Why is no real title available?)
• Elementary induction on abstract structures
• Languages that Capture Complexity Classes
• Upper and lower bounds for first order expressibility

Cited in

(2)

• On the Structure of Logspace Probabilistic Complexity Classes
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs

This page was built for publication: On asymptotic probabilities in logics that capture \(\mathrm{DSPACE}(\log n)\) in presence of ordering

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