On Horn spectra

DOI10.1016/0304-3975(91)90227-SzbMATH Open0723.03023OpenAlexW2042176675MaRDI QIDQ757356FDOQ757356

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

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

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)

Cites Work

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

Cited In (2)

• On the generator problem
• Title not available (Why is that?)

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)