On the relative complexity of some languages in \(NC^ 1\) (Q1124355): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/0020-0190(89)90052-5
+Normal rank
@@ Property / OpenAlex ID @@
+W1968327120
@@ Property / OpenAlex ID: W1968327120 / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
+Normal rank
@@ Property / cites work @@
+Finite monoids and the fine structure of             <i>NC</i>             <sup>1</sup>
+Normal rank
@@ Property / cites work @@
+Constant Depth Reducibility
@@ Property / cites work: Constant Depth Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Parallel computation with threshold functions
@@ Property / cites work: Parallel computation with threshold functions / rank @@
+Normal rank
@@ Property / cites work @@
+Some subclasses of context-free languages in \(NC^ 1\)
+Normal rank
@@ Property / cites work @@
+Q3751010
@@ Property / cites work: Q3751010 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Language recognition by marking automata
@@ Property / cites work: Language recognition by marking automata / rank @@
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On the Tape Complexity of Deterministic Context-Free Languages
+Normal rank