scientific article; zbMATH DE number 3695102

MaRDI QIDQ3888985zbMATH OpenFDO

Authors Larry J. Stockmeyer

Publication date 1979

zbMATH Keywords

combinational complexitysymmetric Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(16)

• On classes of tractable unrestricted regular expressions
• On the complexity of theories of permutations
• The complementation problem for Büchi automata with applications to temporal logic
• Isomorphisms and 1-L reductions
• The complexity of reasoning about knowledge and time. I: Lower bounds
• A 3n-lower bound on the network complexity of Boolean functions
• Complexity results for classes of quantificational formulas
• Practical decidability
• On the equivalence, containment, and covering problems for the regular and context-free languages
• The polynomial-time hierarchy
• On the complexity of some two-person perfect-information games
• The complexity of PDL with interleaving
• Asymptotical behaviour of some non-uniform measures
• Interval logics and their decision procedures. I: An interval logic
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• The complexity of the satisfiability problem for Krom formulas

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 Q3888985)