A bound on the length of a random derivation-search tree in general multi-premise calculi. (English. Russian original) Zbl 0752.03022
Cybernetics 27, No. 3, 462-466 (1991); translation from Kibernetika 1991, No. 3, 112-115 (1991).
Summary: Some complexity bounds are derived for random derivation search trees in Post’s calculus.
MSC:
| 03D15 | Complexity of computation (including implicit computational complexity) |
References:
| [1] | S. Yu. Maslov, ?Search of derivation in general calculi,? Zap. Nauchn. Seminarov LOMI,32, 59?65 (1972). |
| [2] | S. Yu. Maslov and E. D. Rusakov, ?Probabilistic canonical calculi,? Zap. Nauchn. Seminarov LOMI,32, 66?76, (1972). · Zbl 0375.02026 |
| [3] | Yu. N. Kur’erov, ?Equiprobable canonical calculi,? Semiotika Informatika, No. 17, 90?97 (1981). |
| [4] | E. L. Post, ?Formal reduction of the general combinatorial decision problem,? Am. J. Math.,65, No. 2, 197?215 (1943). · Zbl 0063.06327 · doi:10.2307/2371809 |
| [5] | Yu. N. Kur’erov, ?Complexity of derivation search in multi-premise probabilistic canonical calculi,? 7th All-Union Conf. on Problems of Theoretical Cybernetics, Abstracts of Papers [in Russian], Part 1, Irkutsk (1985), pp. 112?113. |
| [6] | V. N. Sachkov, Probabilistic Measures in Combinatorial Analysis [in Russian], Nauka, Moscow (1978). · Zbl 0517.05001 |
| [7] | P. Erdös and A. Rényi, ?On random graphs I,? Public. Math. (Debrecen),6, 290?297 (1959). |
| [8] | J. W. Moon, ?A problem of random trees,? J. Comb. Theory,10, No. 2, 201?205 (1971). · Zbl 0175.20903 · doi:10.1016/0095-8956(71)90043-8 |
| [9] | Z. Dalil, ?On the complexity of regular resolution and the Davis?Putnam procedure,? Theor. Comput. Sci., No.4, 23?46 (1977). · Zbl 0385.68048 · doi:10.1016/0304-3975(77)90054-8 |
| [10] | Z. Galil, ?On resolution with clauses of bounded size,? SIAM J. Comput.,6, 444?459 (1977). · Zbl 0368.68085 · doi:10.1137/0206031 |
| [11] | G. S. Tseitin, ?On derivation complexity in propositional calculi,? Zap. Nauchn. Seminarov LOMI,8, 234?259 (1968). |
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.
