All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 10 Next

Displaying 181 – 200 of 305

Showing per page

On the Complexity of the Hidden Weighted Bit Function for Various BDD Models

Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (2010)

RAIRO - Theoretical Informatics and Applications

Ordered binary decision diagrams (OBDDs) and several more general BDD models have turned out to be representations of Boolean functions which are useful in applications like verification, timing analysis, test pattern generation or combinatorial optimization. The hidden weighted bit function (HWB) is of particular interest, since it seems to be the simplest function with exponential OBDD size. The complexity of this function with respect to different circuit models, formulas, and various...

On the complexity of the Shapley-Scarf economy with several types of goods

Katarína Cechlárová (2009)

Kybernetika

In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete...

On the computation of covert channel capacity

Eugene Asarin, Cătălin Dima (2010)

RAIRO - Theoretical Informatics and Applications

We address the problem of computing the capacity of a covert channel, modeled as a nondeterministic transducer. We give three possible statements of the notion of “covert channel capacity” and relate the different definitions. We then provide several methods allowing the computation of lower and upper bounds for the capacity of a channel. We show that, in some cases, including the case of input-deterministic channels, the capacity of the channel can be computed exactly (e.g. in the form...

On the computational complexity of centers locating in a graph

Ján Plesník (1980)

Aplikace matematiky

It is shown that the problem of finding a minimum k -basis, the n -center problem, and the p -median problem are N P -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal m -center problem is also N P -complete.

On the computational complexity of (O,P)-partition problems

Jan Kratochvíl, Ingo Schiermeyer (1997)

Discussiones Mathematicae Graph Theory

We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.

On the conjecture relating minimax and minimean complexity norms

Peter Růžička, Juraj Wiedermann (1979)

Aplikace matematiky

Using counterexample it has been shown that an algorithm which is minimax optimal and over all minimax optimal algorithms is minimean optimal and has a uniform behaviour need not to be minimean optimal.

On the continuity set of an Omega rational function

Olivier Carton, Olivier Finkel, Pierre Simonnet (2008)

RAIRO - Theoretical Informatics and Applications

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function f has at least one point of continuity and that its continuity set C(f) cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore...

On the decidability of semigroup freeness∗

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....

On the decidability of semigroup freeness

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...

On the decidability of semigroup freeness∗

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....

On the Decidability of the Equivalence Problem for Monadic Recursive Programs

Vladimir A. Zakharov (2010)

RAIRO - Theoretical Informatics and Applications

We present a uniform and easy-to-use technique for deciding the equivalence problem for deterministic monadic linear recursive programs. The key idea is to reduce this problem to the well-known group-theoretic problems by revealing an algebraic nature of program computations. We show that the equivalence problem for monadic linear recursive programs over finite and fixed alphabets of basic functions and logical conditions is decidable in polynomial time for the semantics based on the free monoids...

Currently displaying 181 – 200 of 305