|
Zapiski Nauchnykh Seminarov POMI, 2001, Volume 277, Pages 80–103
(Mi znsl1430)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Upper bound on the height of terms in proofs with bound-depth-restricted cuts
B. Yu. Konev St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
Abstract:
We prove an upper bound on the height of terms occurring in a most general unifier for the case when the set of
term-variables splits to two subsets. A term-variable belongs to the first sub-set iff the depths of all its occurrences coincide, we call such a variable a term-variable of the cut type; otherwise, it belongs to the
second sub-set. We bound from above the height of terms occurring in a most general unifier by the number of
term-variables of not the cut type and size of the given unification problem. This bound implies an upper bound on the size of terms occurring in proofs in a sequent-style calculus with bound-depth-restricted cuts.
Received: 29.08.2000
Citation:
B. Yu. Konev, “Upper bound on the height of terms in proofs with bound-depth-restricted cuts”, Computational complexity theory. Part VI, Zap. Nauchn. Sem. POMI, 277, POMI, St. Petersburg, 2001, 80–103; J. Math. Sci. (N. Y.), 118:2 (2003), 4982–4993
Linking options:
https://www.mathnet.ru/eng/znsl1430 https://www.mathnet.ru/eng/znsl/v277/p80
|
Statistics & downloads: |
Abstract page: | 118 | Full-text PDF : | 47 |
|