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

Asser's problemEXPTIMEgenerator problemHorn sentenceHorn spectrumNEXPTIMEoraclesrelativizationTuring machine

Mathematics Subject Classification ID

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

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

• Complexity classes and theories of finite models
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• Horn sentences
• 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?)
• 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)

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

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)