scientific article; zbMATH DE number 1011685

Publication date: 21 May 1997

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

interconnection networks decision trees communication complexity branching programs complexity measures Boolean circuits multilective VLSI circuits communication protocol models

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (52)

On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ On multi-partition communication complexity ⋮ Comparing the size of NFAs with and without \(\epsilon\)-transitions ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ Quantum weakly nondeterministic communication complexity ⋮ On the OBDD Complexity of the Most Significant Bit of Integer Multiplication ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ Representing regular languages of infinite words using mod 2 multiplicity automata ⋮ An infinite hierarchy of languages defined by dP systems ⋮ On the OBDD complexity of the most significant bit of integer multiplication ⋮ State complexity of cyclic shift ⋮ Unnamed Item ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ A lower bound for integer multiplication on randomized ordered read-once branching programs. ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ Mixed Linear Layouts of Planar Graphs ⋮ Algorithmic complexity of recursive and inductive algorithms ⋮ Transition complexity of language operations ⋮ A survey of results on evolution-communication P systems with energy ⋮ Lower bounds for the transition complexity of NFAs ⋮ Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems ⋮ On the power of randomized multicounter machines ⋮ State complexity of some operations on binary regular languages ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ Larger lower bounds on the OBDD complexity of integer multiplication ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ A note on the size of OBDDs for the graph of integer multiplication ⋮ Nondeterministic state complexity of nested word automata ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ A quick introduction to membrane computing ⋮ On probabilistic pushdown automata ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ On the power of Las Vegas II: Two-way finite automata ⋮ Exact OBDD Bounds for Some Fundamental Functions ⋮ A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs ⋮ Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs ⋮ The advantages of a new approach to defining the communication complexity for VLSI ⋮ Descriptional complexity of regular languages ⋮ On the influence of the variable ordering for algorithmic learning using OBDDs ⋮ Deterministic blow-ups of minimal NFA's ⋮ Construction of Very Hard Functions for Multiparty Communication Complexity ⋮ Quantum communication and complexity. ⋮ On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Lower bounds for linearly transformed OBDDs and FBDDs ⋮ More on deterministic and nondeterministic finite cover automata

This page was built for publication: