scientific article; zbMATH DE number 4209587

MaRDI QIDQ3357533zbMATH OpenFDO

Authors Klaus-Jörn Lange, Peter Rossmanith

Publication date 1990

zbMATH Keywords

augmented push-down automataparallel complexity theoryunambiguity of circuits

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
• Descriptional complexity of unambiguous input-driven pushdown automata
• scientific article; zbMATH DE number 1759446
• Descriptional complexity of (un)ambiguous finite state machines and pushdown automata
• Some results on the structure of unary unambiguous automata
• A unifying approach for multistack pushdown automata
• Unambiguous constrained automata
• Unambiguous constrained automata
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Pushdown automata with bounded nondeterminism and bounded ambiguity

Cited in

(7)

• Unambiguity of circuits
• Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's
• Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
• Depth-first search in directed planar graphs, revisited
• Structure and importance of logspace-MOD class
• Parallel recognition and ranking of context-free languages
• Advocating ownership

This page was built for publication:

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