The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...
We revisit the problem of deciding whether a finitely generated subgroup is a free factor of a given free group . Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of and exponential in the rank of . We show that the latter dependency can be made exponential in the rank difference rank - rank, which often makes a significant change.
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.
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...
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 defined by a quantifier-free first order formula , where the sum of the additive complexities of the polynomials appearing...
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.
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.
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,...
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