Succinctness as a source of complexity in logical formalisms
- 21 March 1999
- journal article
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 97 (1-3), 231-260
- https://doi.org/10.1016/s0168-0072(98)00057-8
Abstract
No abstract availableKeywords
This publication has 39 references indexed in Scilit:
- Abduction from logic programs: Semantics and complexityTheoretical Computer Science, 1997
- Languages represented by Boolean formulasInformation Processing Letters, 1997
- A characterization of the leaf language classesInformation Processing Letters, 1997
- On Completeness for NP via projection translationsPublished by Springer Nature ,1992
- Complete Problems Involving Boolean Labelled Structures and Projection TransactionsJournal of Logic and Computation, 1991
- Why not negation by fixpoint?Journal of Computer and System Sciences, 1991
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- L. Henkin. Some remarks on infinitely long formulas. Infinitistic methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 2-9 September 1959, Państwowe Wydawnictwo Naukowe, Warsaw, and Pergamon Press, Oxford-London-New York-Paris, 1961, pp. 167–183. - Carol R. Karp. Independence proofs in predicate logic with infinitely long expressions. The journal of symbolic logic, vol. 27 no. 2 (for 1962, pub. 1963), pp. 171–188.The Journal of Symbolic Logic, 1965
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965