scientific article

zbMath0642.68084MaRDI QIDQ3783566

Klaus Kriegel, Stephan Waack

Publication date: 1987

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Dyck languagesdecision graphExponential lower boundsreal-time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (5)

A reducibility concept for problems defined in terms of ordered binary decision diagrams ⋮ A lower bound on branching programs reading some bits twice ⋮ A reducibility concept for problems defined in terms of ordered binary decision diagrams ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs ⋮ A very simple function that requires exponential size read-once branching programs.

This page was built for publication: