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

DOI10.1007/3-540-56610-4_90zbMATH Open1497.03050OpenAlexW2154686733MaRDI QIDQ5044764FDOQ5044764

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

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

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)

Cites Work

• Elementary induction on abstract structures
• Languages that Capture Complexity Classes
• Title not available (Why is that?)
• 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)