scientific article; zbMATH DE number 4026854

MaRDI QIDQ3768423zbMATH OpenFDO

Authors Juraj Hromkovič

Publication date 1986

zbMATH Keywords

Chomsky hierarchycommunication complexitycontext-free languageregular languagesVLSI computations

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4112041
• Communication complexity hierarchy
• scientific article; zbMATH DE number 3990864
• scientific article; zbMATH DE number 3881884
• scientific article; zbMATH DE number 1962802

Cited in

(9)

• Linear lower bounds on unbounded fan-in Boolean circuits
• Communication complexity hierarchy
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• scientific article; zbMATH DE number 4112041 (Why is no real title available?)
• scientific article; zbMATH DE number 910357 (Why is no real title available?)
• Lifting query complexity to time-space complexity for two-way finite automata

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 Q3768423)