Completeness proofs for propositional logic with polynomial-time connectives

DOI10.1016/0168-0072(89)90044-4zbMATH Open0678.03004OpenAlexW1980622348WikidataQ126436871 ScholiaQ126436871MaRDI QIDQ1123883FDOQ1123883

Authors: John N. Crossley, Philip Scott 

Publication date: 1989

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(89)90044-4

Recommendations

• Expressive completeness and decidability
• Complexity, decidability and completeness
• scientific article; zbMATH DE number 107724
• scientific article; zbMATH DE number 2072508
• scientific article; zbMATH DE number 1361516

zbMATH Keywords

completenessdecidabilityextensions of propositional calculuspolynomial-time connectives

Mathematics Subject Classification ID

Classical propositional logic (03B05) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70)

Cites Work

• On the Computational Complexity of Algorithms
• Title not available (Why is that?)
• Model theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metamathematical investigation of intuitionistic arithmetic and analysis. With contributions by C. A. Smorynski, J. I. Zucker and W. A. Howard
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Simple characterization of functionally complete one-element sets of propositional connectives

This page was built for publication: Completeness proofs for propositional logic with polynomial-time connectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123883)