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

Page 1 Next

Displaying 1 – 20 of 49

Showing per page

Object oriented institutions to specify symbolic computation systems

César Domínguez, Laureano Lambán, Julio Rubio (2007)

RAIRO - Theoretical Informatics and Applications

The specification of the data structures used in EAT, a software system for symbolic computation in algebraic topology, is based on an operation that defines a link among different specification frameworks like hidden algebras and coalgebras. In this paper, this operation is extended using the notion of institution, giving rise to three institution encodings. These morphisms define a commutative diagram which shows three possible views of the same construction, placing it in an equational algebraic...

On an algorithm to decide whether a free group is a free factor of another

Pedro V. Silva, Pascal Weil (2008)

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

We revisit the problem of deciding whether a finitely generated subgroup H is a free factor of a given free group F . Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of H and exponential in the rank of F . We show that the latter dependency can be made exponential in the rank difference rank ( F ) - rank ( H ) , which often makes a significant change.

On an algorithm to decide whether a free group is a free factor of another

Pedro V. Silva, Pascal Weil (2007)

RAIRO - Theoretical Informatics and Applications

We revisit the problem of deciding whether a finitely generated subgroup H is a free factor of a given free group F. Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of H and exponential in the rank of F. We show that the latter dependency can be made exponential in the rank difference rank(F) - rank(H), which often makes a significant change.

On Graph-Based Cryptography and Symbolic Computations

V. A., Ustimenko (2007)

Serdica Journal of Computing

We have been investigating the cryptographical properties of in nite families of simple graphs of large girth with the special colouring of vertices during the last 10 years. Such families can be used for the development of cryptographical algorithms (on symmetric or public key modes) and turbocodes in error correction theory. Only few families of simple graphs of large unbounded girth and arbitrarily large degree are known. The paper is devoted to the more general theory of directed graphs of large...

On homotopy types of limits of semi-algebraic sets and additive complexity of polynomials

Sal Barone, Saugata Basu (2014)

Journal of the European Mathematical Society

We prove that the number of distinct homotopy types of limits of one-parameter semi-algebraic families of closed and bounded semi-algebraic sets is bounded singly exponentially in the additive complexity of any quantifier-free first order formula defining the family. As an important consequence, we derive that the number of distinct homotopy types of semi-algebraic subsets of ℝ k defined by a quantifier-free first order formula Φ , where the sum of the additive complexities of the polynomials appearing...

On the computation of the GCD of 2-D polynomials

Panagiotis Tzekis, Nicholas Karampetakis, Haralambos Terzidis (2007)

International Journal of Applied Mathematics and Computer Science

The main contribution of this work is to provide an algorithm for the computation of the GCD of 2-D polynomials, based on DFT techniques. The whole theory is implemented via illustrative examples.

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 hardness of approximating some NP-optimization problems related to minimum linear ordering problem

Sounaka Mishra, Kripasindhu Sikdar (2001)

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

We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however,...

On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem

Sounaka Mishra, Kripasindhu Sikdar (2010)

RAIRO - Theoretical Informatics and Applications

We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however,...

Currently displaying 1 – 20 of 49

Page 1 Next