More about recursive structures: descriptive complexity and zero-one laws
- 24 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 334-347
- https://doi.org/10.1109/lics.1996.561361
Abstract
This paper continues our work on infinite, recursive structures. We investigate the descriptive complexity of several logics over recursive structures, including first-order, second-order, and fixpoint logic, exhibiting connections between expressibility of a property and its computational complexity. We then address 0-1 laws, proposing a version that applies to recursive structures and using it to prove several non-expressibility results.Keywords
This publication has 29 references indexed in Scilit:
- Taking it to the limit: on infinite variants of NP-complete problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Functional trees and automorphisms of modelsAlgebra and Logic, 1993
- Infinitary logics and 0–1 lawsInformation and Computation, 1992
- Hamiltonian paths in infinite graphsIsrael Journal of Mathematics, 1991
- 0–1 Laws and decision problems for fragments of second-order logicInformation and Computation, 1990
- The decision problem for the probabilities of higher-order propertiesPublished by Association for Computing Machinery (ACM) ,1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- A zero-one law for logic with a fixed-point operatorInformation and Control, 1985
- On the expressive power of the relational algebraInformation Processing Letters, 1978
- Universal graphs and universal functionsActa Arithmetica, 1964