On Horn spectra

DOI10.1016/0304-3975(91)90227-SzbMath0723.03023OpenAlexW2042176675MaRDI QIDQ757356

Wiesław Szwast

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90227-s

zbMATH Keywords

Turing machinerelativizationNEXPTIMEoraclesAsser's problemEXPTIMEgenerator problemHorn sentenceHorn spectrum

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Model theory.
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• Complexity classes and theories of finite models
• On spectra, and the negative solution of the decision problem for identities having a finite nontrivial model
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Turing machines and the spectra of first-order formulas
• Horn sentences
• On Languages Accepted in Polynomial Time

This page was built for publication: On Horn spectra