Pages that link to "Item:Q1117696"
From MaRDI portal
The following pages link to Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) (Q1117696):
Displaying 50 items.
- On learning width two branching programs (Q293246) (← links)
- A generalization of Spira's theorem and circuits with small segregators or separators (Q342721) (← links)
- The complexity of intersecting finite automata having few final states (Q347114) (← links)
- Hadamard tensors and lower bounds on multiparty communication complexity (Q371197) (← links)
- Comments on ``Arithmetic complexity, Kleene closure, and formal power series'' (Q372962) (← links)
- Linear circuits, two-variable logic and weakly blocked monoids (Q391307) (← links)
- Length of polynomials over finite groups (Q494061) (← links)
- Leaf languages and string compression (Q550251) (← links)
- Descriptional and computational complexity of finite automata -- a survey (Q553312) (← links)
- Optimal advice (Q672755) (← links)
- Knapsack problems for NL (Q673615) (← links)
- \(NC^ 1\): The automata-theoretic viewpoint (Q685708) (← links)
- Towards optimal simulations of formulas by bounded-width programs (Q685723) (← links)
- On the correlation between parity and modular polynomials (Q692898) (← links)
- First-order logics: some characterizations and closure properties (Q715044) (← links)
- The algebraic theory of Parikh automata (Q722218) (← links)
- A moderately exponential time algorithm for \(k\)-IBDD satisfiability (Q722517) (← links)
- Planar and grid graph reachability problems (Q733742) (← links)
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) (Q764326) (← links)
- Complexity theory. Abstracts from the workshop held November 11--17, 2018 (Q782965) (← links)
- Non-uniform automata over groups (Q804303) (← links)
- The parallel complexity of two problems on concurrency (Q811123) (← links)
- On learning embedded midbit functions (Q817826) (← links)
- The equivalence of theories that characterize ALogTime (Q834715) (← links)
- Autoreducibility, mitoticity, and immunity (Q881593) (← links)
- Positive and negative proofs for circuits and branching programs (Q896677) (← links)
- Comparative complexity of quantum and classical OBDDs for total and partial functions (Q906414) (← links)
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} (Q968272) (← links)
- An impossibility gap between width-4 and width-5 permutation branching programs (Q1041742) (← links)
- On the relative complexity of some languages in \(NC^ 1\) (Q1124355) (← links)
- On mod \(p\) transversals (Q1180406) (← links)
- Oracle branching programs and Logspace versus \(P^*\) (Q1183604) (← links)
- Regular languages in \(NC\) (Q1191027) (← links)
- Closure of varieties of languages under products with counter (Q1201878) (← links)
- Extensions to Barrington's M-program model (Q1208406) (← links)
- Succinct representation, leaf languages, and projection reductions (Q1271623) (← links)
- Relating polynomial time to constant depth (Q1274992) (← links)
- Nondeterministic \(NC^1\) computation (Q1276170) (← links)
- Function-algebraic characterizations of log and polylog parallel time (Q1332666) (← links)
- On ACC (Q1346616) (← links)
- Representing Boolean functions as polynomials modulo composite numbers (Q1346617) (← links)
- A note on a theorem of Barrington, Straubing and Thérien (Q1351160) (← links)
- Dyn-FO: A parallel, dynamic complexity class (Q1376403) (← links)
- Predicting nonlinear cellular automata quickly by decomposing them into linear ones (Q1376426) (← links)
- Efficient oblivious branching programs for threshold and mod functions (Q1384527) (← links)
- Universally serializable computation (Q1384538) (← links)
- Finite semigroup varieties defined by programs (Q1390876) (← links)
- Nondeterministic stack register machines (Q1391527) (← links)
- Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) (Q1392020) (← links)
- An algebraic approach to data languages and timed languages (Q1398367) (← links)
