Perfect correspondences between dot-depth and polynomial-time hierarchies (Q2453555): Difference between revisions

@@ Property / cites work @@
+Polynomial operations and hierarchies of concatenation
+Normal rank
@@ Property / cites work @@
+A uniform approach to define complexity classes
@@ Property / cites work: A uniform approach to define complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+The dot-depth hierarchy of star-free languages is infinite
+Normal rank
@@ Property / cites work @@
+On Existentially First-Order Definable Languages and Their Relation to NP
+Normal rank
@@ Property / cites work @@
+On the acceptance power of regular languages
@@ Property / cites work: On the acceptance power of regular languages / rank @@
+Normal rank
@@ Property / cites work @@
+LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
+Normal rank
@@ Property / cites work @@
+Dot-depth of star-free events
@@ Property / cites work: Dot-depth of star-free events / rank @@
+Normal rank
@@ Property / cites work @@
+Simultaneous strong separations of probabilistic and unambiguous complexity classes
+Normal rank
@@ Property / cites work @@
+STACS 2005
@@ Property / cites work: STACS 2005 / rank @@
+Normal rank
@@ Property / cites work @@
+Programs over semigroups of dot-depth one
@@ Property / cites work: Programs over semigroups of dot-depth one / rank @@
+Normal rank
@@ Property / cites work @@
+First-order logic and star-free sets
@@ Property / cites work: First-order logic and star-free sets / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial closure and unambiguous product
@@ Property / cites work: Polynomial closure and unambiguous product / rank @@
+Normal rank
@@ Property / cites work @@
+Fundamentals of Computation Theory
@@ Property / cites work: Fundamentals of Computation Theory / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+An application of the Ehrenfeucht-Fraisse game in formal language theory
+Normal rank
@@ Property / cites work @@
+RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
+Normal rank
@@ Property / cites work @@
+Complete sets and the polynomial-time hierarchy
@@ Property / cites work: Complete sets and the polynomial-time hierarchy / rank @@
+Normal rank