On Horn spectra

DOI10.1016/0304-3975(91)90227-SMaRDI QIDQ757356zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On the generator problem
• scientific article; zbMATH DE number 3916240
• scientific article; zbMATH DE number 4057493
• Fifty years of the spectrum problem: survey and new results
• Horn Sentences of Small Size in Identity Theory

Cites work

• scientific article; zbMATH DE number 3131972 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3485739 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Complexity classes and theories of finite models
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• Horn sentences
• Model theory.
• On Languages Accepted in Polynomial Time
• 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

Cited in

(2)

• On the generator problem
• scientific article; zbMATH DE number 3916240 (Why is no real title available?)

This page was built for publication: On Horn spectra

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