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

DOI10.1007/3-540-56610-4_90zbMath1497.03050MaRDI QIDQ5044764

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

03B70: Logic in computer science

03D15: Complexity of computation (including implicit computational complexity)

60F20: Zero-one laws

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Zero-one laws for \(k\)-variable first-order logic of sparse random graphs

Cites Work

• Unnamed Item
• Upper and lower bounds for first order expressibility
• Elementary induction on abstract structures
• Languages that Capture Complexity Classes