Anzeige der Dokumente 1-10 von 83
On random reductions from sparse sets to tally sets
We show that every sparse set S can be many-one reduced to an appropriate tally set T by a polynomial-time, randomized reduction (see formal definitions below). Since T is in NP if S is in NP, this result can be used to ...
On the complexity of intersecting multiple circles for graphical display
Many experiments in the biomedical field generate vast amounts of data. This is especially true for microarray experiments which measure the expression levels of thousands of genes simultaneously. In this context the display ...
Synthesized and inherited functions - a new computational model for syntax-directed semantics
In this paper we introduce a new formal model for the concept of syntax--directed semantics, called macro attributed tree transducer (for short: mat tree transducer). This model is based on (noncircular) attributed tree ...
A universal unification algorithm based on unification-driven leftmost outermost narrowing
We formalize a universal unification algorithm for the class of equational theories which is induced by the class of canonical, totally-defined, not strictly subunifiable term rewriting systems (for short: ctn-trs). For a ...
Recent highlights in structural complexity theory
Semi-automatic generation of CHR solvers from global constraint automata
Constraint programming often involves global constraints, which have been catalogued in  and for which various custom filtering algorithms have been published. This work presents a semi-automatic generation of CHR solvers ...
Reductions to sets of low information content
This paper is concerned with three basic questions about sparse sets: (1) With respect to what types of reductions might NP have hard or complete sparse sets? (2) If a set A reduces to a sparse set, does it follow that A ...
On the power of generalized MOD-classes
We investigate the computational power of the new counting class ModP which generalizes the classes ModpP, p prime. We show that ModP is polynomial-time truth-table equivalent in power to #P and that ModP is contained in ...
Reliable reductions, high sets and low sets
Measuring the information content of a set by the space-bounded Kolmogorov complexity of its characteristic sequence, we investigate the (non-uniform) complexity of sets A in EXPSPACE/poly that reduce to some set having ...
On a monotonic semantic path ordering
The semantic path ordering preceq_spo is an ordering that allows to prove termination of term rewriting systems. Unlike other such orderings, it is not monotonic. We construct two monotonic suborderings preceq_cspo, ...