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

DOI10.1006/INCO.1995.1064zbMATH Open0826.68080OpenAlexW2035470579MaRDI QIDQ1892887FDOQ1892887

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

Recommendations

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

zbMATH Keywords

unambiguityuniform circuitsAuxPDA classes

Mathematics Subject Classification ID

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

Cited In (13)

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

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)