Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits

DOI10.1006/INCO.1995.1064MaRDI QIDQ1892887zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

unambiguityuniform circuitsAuxPDA classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4209587
• Making Nondeterminism Unambiguous
• Properties that characterize LOGCFL

Cited in

(13)

• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Advocating ownership
• scientific article; zbMATH DE number 1759446 (Why is no real title available?)
• Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract)
• Unambiguous computations and locally definable acceptance types
• scientific article; zbMATH DE number 4131657 (Why is no real title available?)
• Properties that characterize LOGCFL
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Making Nondeterminism Unambiguous
• scientific article; zbMATH DE number 4209587 (Why is no real title available?)
• Unambiguity of circuits
• Data independence of read, write, and control structures in PRAM computations
• Power of counting by nonuniform families of polynomial-size finite automata

This page was built for publication: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892887)