Infinitary queries and their asymptotic probabilities. II. Properties definable in least fixed point logic

DOI10.1002/RSA.3240050120zbMath0828.03011OpenAlexW2061090477MaRDI QIDQ4288891

Jerzy Tyszkiewicz

Publication date: 28 September 1995

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240050120

zbMATH Keywords

computational complexityexpressive powerpartial ordersasymptotic combinatoricsleast fixed-point logicrandom \(r\)-regular graphsasymptotic properties of classes of finite structurespartial fixed point logicslow growing classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Counting finite models ⋮ Unnamed Item

Cites Work

• Elementary induction on abstract structures
• Unnamed Item

This page was built for publication: Infinitary queries and their asymptotic probabilities. II. Properties definable in least fixed point logic