Infinitary queries and their asymptotic probabilities. II: Properties definable in least fixed point logic. (English) Zbl 0828.03011
[For Part I see Lect. Notes Comput. Sci. 626, 396-409 (1992; Zbl 0819.68080).]
The paper is devoted to the study of asymptotic properties of classes of finite structures. The author develops almost complete theories of asymptotic probabilities of the sentences in least fixed-point logic (LFP) and partial fixed-point logic (PFP), and investigates their computational complexity. Section 1 deals with definitions, logical background, and the key results on the expressive power of LFP. Section 2 contains the main results, centred on the statement that the almost sure theory of LFP sentences is recursively approximable. Section 3 provides three interesting examples of applying the obtained results: slow growing classes, partial orders, and random \(r\)-regular graphs. In the final Section 4, the author remarks that all the results proved for LFP hold for PFP as well.
The paper is devoted to the study of asymptotic properties of classes of finite structures. The author develops almost complete theories of asymptotic probabilities of the sentences in least fixed-point logic (LFP) and partial fixed-point logic (PFP), and investigates their computational complexity. Section 1 deals with definitions, logical background, and the key results on the expressive power of LFP. Section 2 contains the main results, centred on the statement that the almost sure theory of LFP sentences is recursively approximable. Section 3 provides three interesting examples of applying the obtained results: slow growing classes, partial orders, and random \(r\)-regular graphs. In the final Section 4, the author remarks that all the results proved for LFP hold for PFP as well.
Reviewer: N.Curteanu (Iaşi)
MSC:
| 03C13 | Model theory of finite structures |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 03D15 | Complexity of computation (including implicit computational complexity) |
Keywords:
asymptotic combinatorics; random \(r\)-regular graphs; asymptotic properties of classes of finite structures; least fixed-point logic; partial fixed point logic; computational complexity; expressive power; slow growing classes; partial ordersCitations:
Zbl 0819.68080References:
| [1] | and , Fixpoint extensions of first-order logic and Datalog-like languages, Proc. 4th IEEE Symp. on Logic in Computer Science, 1989, pp. 71–79. |
| [2] | Barwise, J. Symbolic Logic 42 pp 292– (1977) |
| [3] | and , Model Theory, North Holland, Amsterdam, The Netherlands, 1972. |
| [4] | Random Graphs, Academic, London, England, 1985. |
| [5] | Compton, Adv. Math. 65 pp 65– (1987) |
| [6] | 0–1 laws in logic and combinatorics, in Proc. NATO Advanced Study Institute on Algorithms and Order, Ed., Reidel, Dordrecht, The Netherlands, 1988. |
| [7] | Compton, Inf. Comput. 78 pp 108– (1988) |
| [8] | Compton, J. Combinat. Theory, Ser. A 50 pp 110– (1989) |
| [9] | Compton, Ann. Pure Applied Logic 36 pp 207– (1987) |
| [10] | On local and nonlocal properties, in Logic Colloquium ’81. Ed., North Holland, Amsterdam, The Netherlands, 1982, pp. 106–115. |
| [11] | and , Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979. · Zbl 0426.68001 |
| [12] | Immerman, J. Comput. Syst. Sci. 25 pp 76– (1982) |
| [13] | Immerman, Inf. Control 68 pp 86– (1986) |
| [14] | On asymptotic probabilities of inductive queries and their decision problem, in Logics of Programs, Brooklyn, June 1985, Lecture Notes in Computer Science 193, Springer-Verlag, New York, 1985, pp. 153–166. |
| [15] | and , 0–1 laws for infinitary logics, Proc. 5th IEEE Symp. on Logic in Computer Science, 1990, pp. 156–167. |
| [16] | and , On the expressive power of Datalog: tools and a case study, Proc. 9th ACM Symp. on Principles of Database Systems, 1990, pp. 61–71. |
| [17] | Łuczak, J. Am. Math. Soc. 4 pp 451– (1991) |
| [18] | Elementary Induction on Abstract Structures, North Holland, Amsterdam, the Netherlands 1974. · Zbl 0307.02003 |
| [19] | Spencer, Order |
| [20] | Tyszkiewicz, Proc. CSL ’91 in Berne (1991) |
| [21] | Complexity of relational query languages, 14th Symposium on Theory of Computation 1982, pp. 137–146. |
| [22] | Winkler, Order 1 pp 317– (1985) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
