scientific article; zbMATH DE number 1061261

Publication date 15 September 1997

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35) Abstract and axiomatic computability and recursion theory (03D75) Computability and recursion theory (03Dxx) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Theory of computing (68Qxx)

Recommendations

scientific article; zbMATH DE number 5810075
Computability theory
Computability theory
scientific article; zbMATH DE number 1955470
scientific article; zbMATH DE number 192944
Theory of computation
scientific article; zbMATH DE number 194974
scientific article; zbMATH DE number 6164359
scientific article; zbMATH DE number 1052322
Computability and complexity theory

Cited in

(43)

The complexity of satisfiability problems: Refining Schaefer's theorem
A combinatorial constraint satisfaction problem dichotomy classification conjecture
Bases for Boolean co-clones
A surprising permanence of old motivations (a not-so-rigid story)
Toward a generalized computability theory
The theory of computability developed in terms of satisfaction
Learnability of quantified formulas.
The concept of computability
Definability of Boolean function classes by linear equations over \(\mathbf{GF}(2)\)
The complexity of problems for quantified constraints
Turing computability: structural theory
Enumerating teams in first-order team logics
The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
Sequential?
Parameterized complexity of CTL
The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I
The Foundations of Computability Theory
scientific article; zbMATH DE number 5778850 (Why is no real title available?)
THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
On the applicability of Post's lattice
The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\)
The tractability of model-checking for LTL: the good, the bad, and the ugly fragments
The Foundations of Computability Theory
Parametrised complexity of satisfiability in temporal logic
Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
Parameterised complexity of model checking and satisfiability in propositional dependence logic
Parameterized complexity of propositional inclusion and independence logic
The complexity of satisfiability for fragments of hybrid logic. I.
Temporal team semantics revisited
The complexity of circumscriptive inference in Post's lattice
Trichotomies in the complexity of minimal inference
Recognizing frozen variables in constraint satisfaction problems
H-coloring dichotomy revisited
The complexity of constraint satisfaction games and QCSP
Composition of Post classes and normal forms of Boolean functions
On some enumerative aspects of generalized associahedra
Towards a dichotomy theorem for the counting constraint satisfaction problem
On a quasi-ordering on Boolean functions
On Boolean primitive positive clones
Structure identification of Boolean relations and plain bases for co-clones
Generalized modal satisfiability
Information loss in knowledge compilation: a comparison of Boolean envelopes

This page was built for publication:

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