Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
From MaRDI portal
Publication:1892887
DOI10.1006/inco.1995.1064zbMath0826.68080OpenAlexW2035470579MaRDI QIDQ1892887
Peter Rossmanith, Rolf Niedermeier
Publication date: 10 July 1995
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/16a72da2c491e522a2a5d585c3d7bb2580d332e1
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Unambiguous computations and locally definable acceptance types ⋮ Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract) ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds
