Polynomial-time computation via local inference relations

DOI10.1145/566385.566387zbMath1365.68202arXivcs/0007020OpenAlexW2151097580MaRDI QIDQ5738964

David Allen McAllester, Robert L. Givan

Publication date: 13 June 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0007020

zbMATH Keywords

automated reasoningdecision proceduresdescriptive complexity theory

Mathematics Subject Classification ID

Database theory (68P15) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Related Items

Modular proof systems for partial functions with Evans equality, Automatic decidability and combinability, On Hierarchical Reasoning in Combinations of Theories, Locality Results for Certain Extensions of Theories with Bridging Functions, A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems, On Local Reasoning in Verification, On Interpolation and Symbol Elimination in Theory Extensions, Analyzing innermost runtime complexity of term rewriting by dependency pairs