scientific article; zbMATH DE number 1061261

zbMath0879.03013MaRDI QIDQ4354427

Nicholas J. Pippenger

Publication date: 15 September 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

regular expressionsvarietiesambiguityfinite automatamonoidscontext-free languagesregular languageshalting problemcomputabilitycylindersindex setsdegreesformal power seriespriority methodTuring computabilityprimitive recursionaperiodicityrecursion theoremcreative setsreducibilitiesrational conesoracle machinesabstract complexity theorylogical expressionsrecursive isomorphismsrecursive ennumerability

Mathematics Subject Classification ID

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

Related Items

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