1. On the elimination of quantifier-free cuts
- Author
-
Weller, Daniel
- Subjects
- *
COMPUTATIONAL complexity , *FIRST-order logic , *EXPONENTIAL functions , *ELIMINATION (Mathematics) , *MATHEMATICAL logic - Abstract
Abstract: When investigating the complexity of cut-elimination in first-order logic, a natural subproblem is the elimination of quantifier-free cuts. So far, the problem has only been considered in the context of general cut-elimination, and the upper bounds that have been obtained are essentially double exponential. In this note, we observe that a method due to Dale Miller can be applied to obtain an exponential upper bound. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF