Anzeige der Dokumente 1-10 von 14
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 ...
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
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, ...
Lowness and the complexity of sparse and tally descriptions
We investigate the complexity of obtaining sparse descriptions for sets in various reduction classes to sparse sets. Let A be a set in a certain reduction class R(SPARSE) to the class of sparse sets. Then we are interested ...
Correct configuration of process variants in Provop
When engineering process-aware information systems (PAISs) one of the fundamental challenges is to cope with the variability of business processes. While some progress has been achieved regarding the configuration of process ...