Unambiguity of circuits
From MaRDI portal
Publication:1208408
DOI10.1016/0304-3975(93)90255-RzbMath0774.68047OpenAlexW2014319104MaRDI QIDQ1208408
Publication date: 16 May 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90255-r
circuitsalternating Turing machines\(NC\)auxiliary pushdown automataparallel complexity theoryparallel random-access machines
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
Depth-first search in directed planar graphs, revisited ⋮ Unambiguous computations and locally definable acceptance types ⋮ Parallel recognition and ranking of context-free languages ⋮ Positive and negative proofs for circuits and branching programs ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Nondeterministic \(NC^1\) computation ⋮ Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel time O(log n) recognition of unambiguous context-free languages
- Some subclasses of context-free languages in \(NC^ 1\)
- Tree-size bounded alternation
- On uniform circuit complexity
- Properties that characterize LOGCFL
- Simulation of Parallel Random Access Machines by Circuits
- A taxonomy of problems with fast parallel algorithms
- Alternation
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- On Relating Time and Space to Size and Depth
- On the Tape Complexity of Deterministic Context-Free Languages
- Parallel RAMs with owned global memory and deterministic context-free language recognition
- A unified approach to models of synchronous parallel machines
- Parallelism in random access machines
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: Unambiguity of circuits
