Complexity, decidability and completeness
From MaRDI portal
Publication:5480615
DOI10.2178/jsl/1146620150zbMath1118.03029OpenAlexW2042347326MaRDI QIDQ5480615
Douglas Cenzer, Jeffery B. Remmel
Publication date: 3 August 2006
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/jsl/1146620150
Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Categoricity and completeness of theories (03C35)
Cites Work
- Unnamed Item
- Complexity-theoretic algebra. II: Boolean algebras
- Polynomial-time versus recursive models
- Polynomial-time Abelian groups
- Recursively presented games and strategies
- Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
- Fast Multiple-Precision Evaluation of Elementary Functions
- Feasible Graphs and Colorings
- Class groups of integral group rings