waashk/dblp huggingface dataset:
on the computability of walsh functions. the haar and the walsh functions are proved to be computable with respect to the fine-metric df which is induced from the infinite product ω = {0,1}{1,2,...} with the weighted product metric dc of the discrete metric on {0, 1}. although they are discontinuous functions on [0, 1] with respect to the euclidean metric, they are continuous functions on (ω, dc) and on ([0, 1], df).on (ω, dc), computable real-valued cylinder functions, which include the walsh functions, become computable and every computable function can be approximated effectively by a computable sequence of cylinder functions. the metric space ([0, 1], df) is separable but not complete nor effectively complete. we say that a function on [0, 1] is uniformly fine-computable if it is sequentially computable and effectively uniformly continuous with respect to the metric df. it is proved that a uniformly fine-computable function is essentially a computable function on ω.it is also proved that walsh-fourier coefficients of a uniformly fine-computable function f form a computable sequence of reals and there exists a subsequence of the walsh-fourier series which fine-converges effectively uniformly to f.
on state-alternating context-free grammars. state-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the chomsky hierarchy as well as to some well-known complexity classes. in particular, state-alternating context-free grammars are compared to alternating context-free grammars (theoret. comput. sci. 67 (1989) 75-85) and to alternating pushdown automata. further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated.
some minimum merging networks. let m(m, n) be the minimum number of comparators which constructs an (m, n)-merging network. batcher's odd-even merge, which is a merging network constructed by his algorithm, provides the best upper bound for m(m, n) to date. recently iwata (inform. and comput. 168 (2001) 187) analyzed the property of leftmost comparators, and showed m(m1 + m2, n) ≥ [(m(m1, n) + m(m2, n) + m1 + m2 + n - 2)/2]. we extend iwata's proofs and show that batcher's (6, 8k + 7)-, (9, 16k + 9)-, (7, 8)-merging networks are optimal for all k ≥ 0.in batcher's (m, n)-merging network, the ith smallest element out of m elements and another ith smallest element out of n elements are first compared for all i (1 ≤ i ≤ min{m, n}). under an assumption of existence of such min{m, n} comparators in optimal (m, n)-merging networks, we show that m(n, n) = m(n - 1, n) + 1 = m(n - 2, n) + 3.
counting by quantum eigenvalue estimation. for every "computation" there corresponds the physical task of manipulating a starting state into an output state with a desired property. as the classical theory of physics has been replaced by quantum physics, it is interesting to consider the capabilities of a computer that can exploit the distinctive quantum features of nature. the extra capabilities seem enormous. for example, with only an expected o(square rootn) evaluations of a function f : {0; 1; : : : ; n - 1} &rarr; {0; 1}, we can find a solution to f(x) = 1 provided one exists. another example is the ability to 1nd efficiently the order of an element g in a group by using a quantum computer to estimate a random eigenvalue of the unitary operator that multiplies by g in the group. by using this eigenvalue estimation algorithm to estimate an eigenvalue of the unitary operator used in quantum searching we can approximately count the number of solutions to f(x) = 1. this paper describes this eigenvector approach to quantum counting and related algorithms.
on primitive recursive algorithms and the greatest common divisor function. we establish linear lower bounds for the complexity of non-trivial, primitive recursive algorithms from piecewise linear given functions. the main corollary is that logtime algorithms for the greatest common divisor from such givens (such as stein's) cannot be matched in efficiency by primitive recursive algorithms from the same given functions. the question is left open for the euclidean algorithm, which assumes the remainder function.
on the relationship between compact regularity and gentzen's cut rule. the patch topology on a stably compact space, generalizing the lawson topology on a domain, is a coreflection of stably compact spaces in compact regular spaces. this paper investigates compact regularity and the patch coreflection in multilingual sequent calculus (mls), which can be regarded as a category of predicative representations of stably compact spaces. an object of mls is a certain sort of generalization of the positive fragment of gentzen's sequent calculus. we show that an object of mls represents a compact regular space if and only if every sequent arises as an instance of gentzen's cut rule with complete freedom to choose the placement of the cut formula.the relationship between compact regularity and gentzen's cut rule is further explicated by the patch coreflection in mls. the construction is a universal solution (up to a certain equivalence of tokens) to the problem of adding opposites to a logic, i.e., tokens that obey gentzen's rules for negation. in the spectral case, this is equivalent to adding boolean complements. the paper closes by considering the full subcategory of mls consisting of objects with opposites. by taking contrapositives of sequents, we obtain an anti-involution on morphisms making this category equivalent to the freyd/scedrov allegory of compact regular spaces and closed binary relations. moreover, the category of "maps" of this allegory is predicatively equivalent to the image of the patch functor.
recursion and corecursion have the same equational logic. this paper is concerned with the equational logic of definitions whose semantics is given in terms of final coalgebra maps. the framework for our study is iteration theories (cf. e.g. bloom and ésik, iteration theories: the equational logic of iterative processes, eatcs monographs on theoretical computer science, springer, berlin, 1993; theoret. comput. sci. 179 (1-2) (1997)), recently re-introduced as models of the flr0 fragment of the formal language of recursion (hurkens et al., j. symbolic logic 63 (2) (1998) 45; mos chovakis, j. symbolic logic 54 (1989) 1216; in: m.l. dalla chiara et al. (eds.), logic and scientific methods, kluwer, dordrecht, 1997, p. 179). we present a new class of iteration theories derived from final coalgebras. this allows us to reason with a number of types of fixed-point equations which heretofore seemed to require metric or order-theoretic ideas. all of the work can be done using finality properties and equational reasoning. having a semantics, we obtain the following completeness result: the equations involving fixed-point terms which are valid for final coalgebra interpretations are exactly those valid in a number of contexts pertaining to recursion. for example, they coincide with the equations valid for least-fixed-point recursion on dcpo's. we also present a new version of the proof of the well-known completeness result for iteration theories (see ésik, comput. linguistics comput. languages 4 (1982) 95; hurkens et al., 1998). our work brings out a connection between coalgebraic reasoning and recursion.
relating casl with other specification languages: the institution level. in this work, we investigate various specification languages and their relation to casl, the recently developed common algebraic specification language. in particular, we consider the languages larch, obj3 and functional cafeobj, act one, asf, and hep-theories, as well as various sublanguages of casl. all these languages are translated to an appropriate sublanguage of casl.the translation mainly concerns the level of specification in-the-small: the logics underlying the languages are formalized as institutions, and representations among the institutions are developed. however, it is also considered how these translations interact with specification in-the-large.thus, we obtain, on the one hand, translations of any of the above-mentioned specification languages to an appropriate sublanguage of casl. this allows us to take libraries and case studies that have been developed for other languages and re-use them in casl.on the other hand, we set up institution representations going from the casl institution (and some of its subinstitutions) to simpler subinstitutions. given a theorem proving tool for such a simpler subinstitution, with the help of a representation, it can also be used for a more complex institution. thus, first-order theorem provers and conditional term rewriting tools become usable for casl.
dependable computing: an overview. dependability is carving out a more and more important place in computer science. to introduce this special issue on dependable computing, we present a synthetic overview of this domain, intended for computer scientists. this paper attempts neither to enumerate nor to detail the numerous particular research work leads on this theme. it rather introduces the requirements from which research activities are stemmed. it synthesises the various issues handled by these activities as well as the various solutions they propose. the content aims at providing to computer scientists a pedagogical survey of the various problems, concepts and classes of studies relating to dependable computing. supplying a synthetic article does not allow, in particular, numerous contributory persons and teams to be quoted or publications to be listed. the five following papers of this special issue tackle deeply specific aspects of this area.
rank inequalities and separation algorithms for packing designs and sparse triple systems. combinatorial designs find numerous applications in computer science, and are closely related to problems in coding theory. packing designs correspond to codes with constant weight; 4-sparse partial steiner triple systems (4-sparse pstss) correspond to erasure-resilient codes that are useful in handling failures in large disk arrays (chee, colbourn, ling, discrete appl. math., to appear; hellerstein, gibson, karp, katz, paterson, algorithmica 12 (1994) 182-208). the study of polytopes associated with combinatorial problems has proven to be important for both algorithms and theory, but only recently the study of design polytopes has been pursued (moura, math. appl. 368 (1996) 227-254; moura, ph.d. thesis, university of toronto, 1999; moura, proc. seventh annu. european symp. prague, 1999, lecture notes in computer science, vol. 1643, springer, berlin, 1999, pp. 462-475; wengrzik, master's thesis, universität berlin, 1995; zehendner, doctoral thesis, universität augsburg, 1986). in this article, we study polytopes associated with t-(v,k,λ) packing designs and with m-sparse pstss. subpacking and l-sparseness inequalities are introduced and studied. they can be regarded as rank inequalities for the independence systems associated with these designs. conditions under which subpacking inequalities define facets are derived; in particular, those which define facets for pstss are determined. for m ≥ 4, the l-sparseness inequalities with 2 ≤ l ≤ m are proven to induce facets for the m-sparse psts polytope; this proof uses extremal families of pstss known as erdös configurations. separation algorithms for these inequalities are proposed. we incorporate some of the sparseness inequalities in a polyhedral algorithm, and determine maximal 4-sparse psts(v), v ≤ 16. an upper bound on the size of m-sparse pstss is presented.
marcus t-contextual grammars and cut hierarchies and monotonicity for restarting automata. the t-contextual grammars are generalizations of marcus contextual grammars, which insert t contexts in each derivation step. if the selection mappings are regular and satisfy an additional locality restriction, then these grammars correspond in their expressive power to restarting automata with cut-index t. in the first part of the paper classes of languages are studied that are accepted by certain types of restarting automata with limited cut-index. as already r-automata with cut-index 1 accept np-complete languages, additional restrictions in the form of certain monotonicity conditions are also considered. without the locality restriction t-contextual grammars with regular selection correspond to t- rr-automata with cut-index one. these are rr-automata that are allowed to perform up to t deletion operations in each cycle that each delete a single factor only. in the second part of the paper the expressive power of these automata is studied, where the focus is on the special case that certain monotonicity conditions are satisfied.
the dnf exception problem. given a disjunctive normal form (dnf) expression ϕ and a set a of vectors satisfying the expression, called the set of exceptions, we would like to update ϕ to get a new dnf which is false on a, and otherwise is equivalent to ϕ. is there an algorithm with running time polynomial in the number of variables, the size of the original formula and the number of exceptions, which produces an updated formula of size bounded by a certain type of function of the same parameters?we give an efficient updating algorithm, which shows that the previously known best upper bound for the size of the updated expression is not optimal in order of magnitude. we then present a lower bound for the size of the updated formula in terms of the parameters, which is the first known lower bound for this problem. we also consider the special case (studied previously in the complexity theory of disjunctive normal forms) where the initial formula is identically true, and give efficient updating algorithms, providing new upper bounds for the size of the updated expression.
conditional complexity and codes. let x and y be binary strings. we prove that there exists a program p of size about k(x|y) that maps y tox and has small complexity when x is known (k(p|x)0)*#8776;0). having in mind the parallelism between shannon information theory and algorithmic information theory, one can say that this result is parallel to wolf-slepian and k&ouml;rner-csiszar-marton theorems, see (i. csiszar and j. k&ouml;rner, information theory, coding theorems for discrete memoryless systems, akad&eacute;miai kiad&oacute;, budapest, 1981). we show also that for any three stringsx,y,z of length at most n the length of the shortest program p that maps both y and z to x (i.e., p(y)=p(z)=x) equals max(k(x|y),k(x|z)+o(logn.
the definable criterion for definability in presburger arithmetic and its applications. in section 1 of present paper we construct a formula φn(a) of presburger arithmetic (integers with addition and order) with additional n-ary predicate variable a. this formula is true if and only if predicate a is definable in presburger arithmetic (theorem 2).this formula is used to prove the following facts: (1) given a finite synchronous automaton recognizing a set of n-tuples of integers written in positional notation one can effectively decide whether this set is definable in presburger arithmetic; (2) every predicate (set of n-tuples of integers) recognizable in two essentially different positional systems is definable in presburger arithmetic. the last result was proved by cobham (math. systems theory, 3(2) (1969) 186) for the case n= 1. in general case both (1) and (2) were proved by semenov (ph.d. thesis, moscow state university; siberian math. j. 18(2) (1977) 403) (semenov's proofs are very difficult).
one application of real-valued interpretation of formal power series. we define two natural properties of context-free grammars. the first property generalizes linearity and the second property strengthens nonlinearity. a language generated by an unambiguous grammar of the first type is called the language with weak linear structure and a language generated by an unambiguous grammar of the second type is called the language with strong nonlinear structure. our main theorem states that the family of unambiguous grammars generating languages with weak linear structure and the family of unambiguous grammars generating languages with strong nonlinear structure are effectively separable.
kolmogorov entropy in the context of computability theory. we consider the overgraph of the kolmogorov entropy function and study whether it is a complete enumerable set with respect to different types of reductions. it turns out that (for any type of entropy) the overgraph of the conditional entropy function is m-.
almost periodic sequences. this paper studies properties of almost periodic sequences (also known as uniformly recursive).a sequence is almost periodic if for every finite string that ccurs infinitely many times in the sequence there exists a number m such that every segment of length m contains an ccurrence of the word.we study closure properties of the set of almost periodic sequences, ways to generate such sequences (including a general way), computability issues and kolmogorov complexity of prefixes of almost periodic sequences.
a general method to construct oracles realizing given relationships between complexity classes. we present a method to prove oracle results of the following type. let k_1, \ldots, k_{2n}, and l_1, \ldots, l_{2m} be complexity classes. our method provides a general framework for constructing an oracle a such that k^a_{2i-1} \neq k^a_{2i} for i=1, \ldots, n and l^a_{2j-1} = l^a_{2j} for j=1, \ldots, m. using that method we prove several results of this kind. the hardest of them is the existence of an oracle a such that p^a \neq np^a, p^a = bpp^a, and both conp^a-sets and np^a-sets are p^a-separable. we exhibit also two theorems that cannot be proved by that method.
evolutionary computation and wright's equation. in this paper, wright's equation formulated in 1931 is proven and applied to evolutionary computation. wright's equation shows that evolution is doing gradient ascent in a landscape defined by the average fitness of the population. the average fitness w is defined in terms of marginal gene frequencies pi. wright's equation is only approximately valid in population genetics, but it exactly describes the behavior of our univariate marginal distribution algorithm (umda). we apply wright's equation to a specific fitness function defined by wright. furthermore we introduce mutation into wright's equation and umda. we show that mutation moves the stable attractors from the boundary into the interior. we compare wright's equation with the diversified replicator equation. we show that a fast version of wright's equation gives very good results for optimizing a class of binary fitness functions.
bounded time-stamping in message-passing systems. consider a distributed system running a protocol in which processes exchange information by passing messages. the gossip problem for the protocol is the following: whenever a process q receives a message from another process p, q must be able to decide which of p and q has more recent information about r, for every other process r in the system. with this data, q is in a position to update its knowledge about the global state of the system.we propose a solution wherein to each message of the protocol, the sender adds information about its current state of knowledge about other processes. we do not add any new messages to the underlying computation. the additional information tagged onto each message is uniformly bounded if the channels are bounded. this means that for systems with bounded channels, the overhead of maintaining the latest gossip is a constant, independent of the length of the underlying computation. moreover, gossip information can be used to implement bounded channels by inhibiting the sending of new messages over channels that are potentially full.our solution to the gossip problem has several applications in the analysis of distributed systems. many distributed algorithms rely, either explicitly or implicitly, on the local information available at a process about the global state of the system. using our scheme, each process can ensure that during a computation it always maintains the best possible information about every other process. at a theretical level, the gossip problem plays an important role in formal characterizations of finite-state message-passing systems.
moving policies in cyclic assembly line scheduling. we consider an assembly line problem that occurs in various kinds of production automation. our original motivation lies in the automated manufacturing of pc boards. the assembly line has to process a (potentially infinite) number of identical workpieces in a cyclic fashion. in contrast to common variants of assembly line scheduling, the forward steps are variable and may be smaller than the distance of two stations. therefore, each station may process parts of several workpieces at the same time, and parts of a workpiece may be processed by several stations at the same time. the throughput rate is determined by the number of (cyclic) forward steps, the offsets of the individual forward steps, and the distribution of jobs over the stationary stages between the forward steps. the number of forward steps as well as the offsets are part of the output. however, no matter whether they are part of the input or the output, the optimal assignment of the jobs to the stationary stages is np-hard.we will base our algorithmic considerations on some quite conservative assumptions, which are greatly fulfilled in various application scenarios, including the one in our application: the number of jobs may be huge, but the number of stations and the number of forward steps in an optimal solution are small, the granularity of forward steps is quite coarse, and the processing times of the individual items do not differ by several orders of magnitude from each other. we will present an algorithm that is polynomial and provably deviates from optimality to a negligible extent (under these assumptions). this result may be viewed as an application of fixed-parameter tractability.
precise interprocedural dependence analysis of parallel programs. it is known that interprocedural detection of copy constants and elimination of faint code in parallel programs are undecidable problems, if base statements are assumed to execute atomically. we show that these problems become decidable, if this assumption is abandoned. so, the (unrealistic) idealization from program verification "atomic execution of base statements" introduced in order to simplify matters, actually increases the difficulty of these problems from the point of view of program analysis: amazingly these problems become more tractable if we adopt a less idealized, more realistic model of execution.we introduce an effective abstract domain of antichains of dependence traces that allows us to perform a precise interprocedural dependence analysis in (non-atomically executing) parallel programs. the main idea is to trace sequences of dependences exhibited successively by program executions. we define operations on antichains of dependence traces and show that they precisely abstract the corresponding operations on sets of non-atomic program executions. using these operations, we can analyze dependences by means of an abstract interpretation of constraint systems that characterize sets of program executions of interest. the result of the dependence analysis can in turn be used to detect all copy constants and to eliminate faint code.while the run-time of the algorithms is exponential in the number of program variables, it is polynomial in the program size. hence, they are polynomial-time algorithms if the number of program variables is bounded. in order to justify their overall exponential run-time, we show that both detection of copy constants and elimination of faint code are intractable (np-hard) even when the atomic execution idealization is abandoned. this holds already for parallel programs without loops or procedures.