scientific article

zbMath0631.68068MaRDI QIDQ3768423

Juraj Hromkovič

Publication date: 1986

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

zbMATH Keywords

context-free languageregular languagescommunication complexityChomsky hierarchyVLSI computations

Mathematics Subject Classification ID

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

Related Items (6)

Lifting query complexity to time-space complexity for two-way finite automata ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Linear lower bounds on unbounded fan-in Boolean circuits

This page was built for publication: