waashk/dblp huggingface dataset:
hierarchies of probabilistic and team fin-learning. a fin-learning machine m receives successive values of the function f it is learning and at some moment outputs a conjecture which should be a correct index of f. fin learning has two extensions: (1) if m flips fair coins and learns a function with certain probability p, we have fin (p)-learning. (2) when n machines simultaneously try to learn the same function f and at least k of these machines output correct indices of f, we have learning by a [k,n] fin team. sometimes a team or a probabilistic learner can simulate another one, if their probabilities p1, p2 (or team success ratios k1/n1,k2/n2) are close enough (daley et al., in: valiant, waranth (eds.), proc. 5th annual workshop on computational learning theory, acm press, new york, 1992, pp. 203-217; daley and kalyanasundaram, available from http://www.cs.pitt.edu/~daley/fin/fin.html, 1996). on the other hand, there are cut-points r which make simulation of fin (p2) by fin (p1) impossible whenever p2 < r < p1. cut-points above 10/21 are known (daley and kalyanasundaram, available from (www.cs.pitt.edu/~daley/fin/fin.html, 1996).
computational depth: concept and applications. we introduce computational depth, a measure for the amount of "nonrandom" or "useful" information in a string by considering the difference of various kolmogorov complexity measures. we investigate three instantiations of computational depth: • basic computational depth, a clean notion capturing the spirit of bennett's logical depth. we show that a turing machine m runs in time polynomial on average over the time-bounded universal distribution if and only if for all inputs x, m uses time exponential in the basic computational depth of x. • sublinear-time computational depth and the resulting concept of shallow sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences. we show that every computable set that is reducible to a shallow set has polynomial-size circuits. • distinguishing computational depth, measuring when strings are easier to recognize than to produce. we show that if a boolean formula has a nonnegligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently.
almost complete sets. we show that there is a set that is almost complete but not complete under polynomial-time many-one (p-m) reductions for the class e of sets computable in deterministic time 2lin. here a set in a complexity class c is almost complete for c under some given reducibility if the class of the problems in c that do not reduce to this set has measure 0 in c in the sense of lutz's resource-bounded measure theory. we also show that the almost complete sets for e under polynomial time-bounded length-increasing one-one reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for e. moreover, we obtain similar results for the class exp of sets computable in deterministic time 2poly.
on the approximability of the range assignment problem on radio networks in presence of selfish agents. we consider the range assignment problem in ad-hoc wireless networks in the context of selfish agents: a network manager aims to assigning transmission ranges to the stations in order to achieve strong connectivity of the network within a minimal overallpower consumption. station is not directly controlled by the manager and may refuse to transmit with a certain transmission range because it might be costly in terms of power consumption.we investigate the existence of payment schemes which induce the stations to follow the decisions of a network manager in computing a range assignment, that is, truthful mechanisms for the range assignment problem. we provide both positive and negative results on the existence of truthful vcg-based mechanisms for this np-hard problem. we prove that (i) in general, every polynomial-time truthful vcg-based mechanism computes a solution of cost far-off the optimum, unless p = np and (ii) there exists a polynomial-time truthful vcg-based mechanism achieving constant approximation for practically relevant, still np-hard versions, i.e., the metric and the well-spread case.
a new lower bound for the list update problem in the partial cost model. the optimal competitive ratio for a randomized online list update algorithm is known to be at least 1.5 and at most 1.6, but the remaining gap is not yet closed. we present a new lower bound of 1.50084 for the partial cost model. the construction is based on game trees with incomplete information, which seem to be generally useful for the competitive analysis of online algorithms. 2001 elsevier science b.v.
computational topology: ambient isotopic approximation of 2-manifolds. a fundamental issue in theoretical computer science is that of establishing unambiguous formal criteria for algorithmic output. this paper does so within the domain of computer-aided geometric modeling. for practical geometric modeling algorithms, it is often desirable to create piecewise linear approximations to compact manifolds embedded in r3, and it is usually desirable for these two representations to be "topologically equivalent". though this has traditionally been taken to mean that the two representations are homeomorphic, such a notion of equivalence suffers from a variety of technical and philosophical difficulties; we adopt the stronger notion of ambient isotopy. it is shown here, that for any c2, compact, 2-manifold without boundary, which is embedded in r3, there exists a piecewise linear ambient isotopic approximation. furthermore, this isotopy has compact support, with specific bounds upon the size of this compact neighborhood. these bounds may be useful for practical application in computer graphics and engineering design simulations. the proof given relies upon properties of the medial axis, which is explained in this paper.
two-dimensional pattern matching with rotations. the problem of pattern matching with rotation is that of finding all occurrences of a two-dimensional pattern in a text, in all possible rotations. we prove an upper and lower bound on the number of such different possible rotated patterns. subsequently, given an m × m array (pattern) and an n × n array (text) over some finite alphabet σ, we present a new method yielding an o(n2m3) time algorithm for this problem.
topics in the theory of dna computing. dna computing, or, more generally, molecular computing, is an exciting fast developing interdisciplinary area. research in this area concerns theory, experiments, and applications of dna computing. in this paper, we demonstrate the theoretical developments by discussing a number of selected topics. we also give an introduction to the basic structure of dna and the basic dna processing tools.
image reducing words and subgroups of free groups. a word w over a finite alphabet σ is said to be n-collapsing if for an arbitrary finite automaton a = 〈q,σ_._〉, the inequality |q ċ w| ≤ |q|- n holds provided that |q ċ u| ≤ |q|- n for some word u (depending on a). we give an algorithm to test whether a word is 2-collapsing. to this aim we associate to every word w a finite family of finitely generated subgroups in finitely generated free groups and prove that the property of being 2-collapsing reflects in the property that each of these subgroups has index at most 2 in the corresponding free group. we also find a similar characterization for the closely related class of so-called 2-synchronizing words.
closedness properties in ex-identification. in this paper we investigate in which cases unions of identifiable classes are also necessarily identifiable. we consider identification in the limit with bounds on mindchanges and anomalies. though not closed under the set union, these identification types still have features resembling closedness. for each of them we and n such that (1) if every union of n &minus; 1 classes out of u1, ... , un is identifiable, so is the union of all n classes; (2) there are classes u1, ... ,un&minus;1 such that every union of n&minus;2 classes out of them is identifiable, while the union of n &minus; 1 classes is not. we show that by finding these n we can distinguish which requirements put on the identifiability of unions of classes are satisfiable and which are not. we also show how our problem is connected with team learning. copyright 2001 elsevier science b.v. all rights reserved.
synchronizing monotonic automata. we show that if the state set q of a synchronizing automaton a = 〈q, σ, δ〉 admits a linear order such that for each letter a ∈ σ the transformation δ(_,a) of q preserves this order, then a possesses a reset word of length |q| - 1. we also consider two natural generalizations of the notion of a reset word and provide for them results of a similar flavour.
synchronizing generalized monotonic automata. in an earlier paper, we have studied reset words for synchronizing automata whose states admit a stable linear order. here we show that the same bound on the length of the shortest reset word persists for synchronizing automata satisfying much weaker stability restriction. this result supports our conjecture concerning the length of reset words for synchronizing automata accepting only star-free languages.
sturmian words and a criterium by michaux-villemaire. michaux and villemaire's proof of cobham's theorem relies on the characterization of ultimately periodic words by means of the behaviour of certain repetitions in the word. namely, they consider the length of the smallest shift between repetitions of a given length and the first position at which that smallest shift is observed. in this paper we study those properties for characteristic sturmian words. in particular we answer a question posed by michaux and villemaire in that context.
words derivated from sturmian words. a return word of a factor of a sturmian word starts at an occurrence of that factor and ends exactly before its next occurrence. derivated words encode the unique decomposition of a word in terms of return words. vuillon has proved that each factor of a sturmian word has exactly two return words. we determine these two return words, as well as their first occurrence, for the prefixes of characteristic sturmian words. we then characterize words derivated from a characteristic sturmian word and give their precise form. finally, we apply our results to obtain a new proof of the characterization of characteristic sturmian words which are fixed points of morphisms.
scalar aggregation in inconsistent databases. we consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. we define consistent answers to such queries to be greatest-lowest/least-upper bounds on the value of the scalar function across all (minimal) repairs of the database. we show how to compute such answers. we provide a complete characterization of the computational complexity of this problem. we also show how tractability can be improved in several special cases (one involves a novel application of boyce-codd normal form) and present a practical hybrid query evaluation method.
nivat's processes and their synchronization. this short paper retraces how the notion of synchronization of processes introduced by maurice nivat in 1979 has evolved over more than 20 years.
weighted multirecombination evolution strategies. weighted recombination is a means for improving the local search performance of evolution strategies. it aims to make effective use of the information available, without significantly increasing computational costs per time step. in this paper, the potential speed-up resulting from using rank-based weighted multirecombination is investigated. optimal weights are computed for the infinite-dimensional sphere model, and comparisons with the performance of strategies that do not make use of weighted recombination are presented. it is seen that unlike strategies that rely on unweighted recombination and truncation selection, weighted multirecombination evolution strategies are able to improve on the serial efficiency of the (1 + 1)-es on the sphere. the implications of the use of weighted recombination for noisy optimization are studied, and parallels to the use of rescaled mutations are drawn. the significance of the findings is investigated in finite-dimensional search spaces.
performance analysis of evolution strategies with multi-recombination in high-dimensional rn-search spaces disturbed by noise. the presence of noise in real-world optimization problems poses difficulties to optimization strategies. it is frequently observed that evolutionary algorithms are quite capable of succeeding in noisy environments. intuitively, the use of a population of candidate solutions alongside with some implicit or explicit form of averaging inherent in the algorithms is considered responsible. however, so as to arrive at a deeper understanding of the reasons for the capabilities of evolutionary algorithms, mathematical analyses of their performance in select environments are necessary. such analyses can reveal how the performance of the algorithms scales with parameters of the problem--such as the dimensionality of the search space or the noise strength--or of the algorithms--such as population size or mutation strength. recommendations regarding the optimal sizing of such parameters can then be derived.the present paper derives an asymptotically exact approximation to the progress rate of the (µ/µi, λ)-evolution strategy (es) on a finite-dimensional noisy sphere. it is shown that, in contrast to results obtained in the limit of infinite search space dimensionality, there is a finite optimal population size above which the efficiency of the strategy declines, and that therefore it is not possible to attain the efficiency that can be achieved in the absence of noise by increasing the population size. it is also shown that nonetheless, the benefits of genetic repair and an increased mutation strength make it possible for the multi-parent (µ/µi, λ)-es to far outperform simple one-parent strategies.
synchronizing groups and automata. pin showed that every p-state automaton (p a prime) containing a cyclic permutation and a non-permutation has a synchronizing word of length at most (p - 1)2. in this paper, we consider permutation automata with the property that adding any nonpermutation will lead to a synchronizing word and establish bounds on the lengths of such synchronizing words. in particular, we show that permutation groups whose permutation character over the rationals splits into a sum of only two irreducible characters have the desired property.
games for synthesis of controllers with partial observation. the synthesis of controllers for discrete event systems, as introduced by ramadge and wonham, amounts to computing winning strategies in parity games. we show that in this framework it is possible to extend the specifications of the supervised systems as well as the constraints on the controllers by expressing them in the modal µ-calculus.in order to express unobservability constraints, we propose an extension of the modal µ-calculus in which one can specify whether an edge of a graph is a loop. this extended µ-calculus still has the interesting properties of the classical one. in particular it is equivalent to automata with loop testing. the problems such as emptiness testing and elimination of alternation are solvable for such automata.the method proposed in this paper to solve a control problem consists in transforming this problem into a problem of satisfiability of a µ-calculus formula so that the set of models of this formula is exactly the set of controllers that solve the problem. this transformation relies on a simple construction of the quotient of automata with loop testing by a deterministic transition system. this is enough to deal with centralized control problems. the solution of decentralized control problems uses a more involved construction of the quotient of two automata.this work extends the framework of ramadge and wonham in two directions. we consider infinite behaviours and arbitrary regular specifications, while the standard framework deals only with specifications on the set of finite paths of processes. we also allow dynamic changes of the sets of observable and controllable events.
two-dimensional iterated morphisms and discrete planes. iterated morphisms of the free monoid are very simple combinatorial objects which produce infinite sequences by replacing iteratively letters by words. the aim of this paper is to introduce a formalism for a notion of two-dimensional morphisms; we show that they can be iterated by using local rules, and that they generate two-dimensional patterns related to discrete approximations of irrational planes with algebraic parameters. we associate such a two-dimensional morphism with any usual pisot unimodular one-dimensional iterated morphism over a three-letter alphabet.
a generalization of the language of ukasiewicz coding rooted planar hypermaps. we introduce a coding of rooted planar hypermaps by words of a language generalizing the language of lukasiewicz. this code is obtained by a geometrical decomposition of hypermaps and leads to a new enumeration of rooted planar hypermaps with respect to the number of vertices, hyperfaces and hyperedges.
a note on first-order projections and games. we show how the fact that there is a first-order projection from the problem transitive closure (tc) to some other problem ω enables us to automatically deduce that a natural game problem, lg(ω), whose instances are labelled instances of ω, is complete for pspace (via log-space reductions). our analysis is strongly dependent upon the reduction from tc to ω being a logical projection in that it fails should the reduction be, for example, a log-space reduction or a quantifier-free first-order translation.
justified common knowledge. in this paper we introduce the justified knowledge operator j with the intended meaning of j ϕ as 'there is a justification for ϕ.' though justified knowledge appears here in a case study of common knowledge systems, a similar approach is applicable in more general situations. first we consider evidence-based common knowledge systems obtained by augmenting a multi-agent logic of knowledge with a system of evidence assertions t:ϕ, reflecting the notion 't is an evidence for ϕ,' such that evidence is respected by all agents. justified common knowledge is obtained by collapsing all evidence terms into one modality j. we show that in standard situations, when the base epistemic systems are t, s4, and s5, the resulting justified common knowledge systems are normal modal logics, which places them within the scope of well-developed machinery applicable to modal logic: kripke-style epistemic models, normalized proofs, automated proof search, etc. in the aforementioned situations, the intended semantics of justified knowledge is supported by a realization theorem stating that for any valid fact about justified knowledge, one could recover its constructive meaning by realizing all occurrences of justified knowledge modalities jϕ by appropriate evidence terms t:ϕ.
combining test case generation and runtime verification. software testing is typically an ad hoc process where human testers manually write test inputs and descriptions of expected test results, perhaps automating their execution in a regression suite. this process is cumbersome and costly. this paper reports results on a framework to further automate this process. the framework consists of combining automated test case generation based on systematically exploring the input domain of the program with runtime verification, where execution traces are monitored and verified against properties expressed in temporal logic. capabilities also exist for analyzing traces for concurrency errors, such as deadlocks and data races. the input domain of the program is explored using a model checker extended with symbolic execution. properties are formulated in an expressive temporal logic. a methodology is advocated that automatically generates properties specific to each input rather than formulating properties uniformally true for all inputs. the paper describes an application of the technology to a nasa rover controller.
a fast natural algorithm for searching. in this note we present two natural algorithms--one for sorting, and another for searching a sorted list of items. both algorithms work in o(√n) time, n being the size of the list. a combination of these algorithms can search an unsorted list in o(√n) time, an impossibility for classical algorithms. the same complexity is achieved by grover's quantum search algorithm; in contrast to grover's algorithm which is probabilistic, our method is guaranteed correct. two applications will conclude this note.
an improved analysis of goemans and williamson's lp-relaxation for max sat. for max sat, which is a well-known np-hard problem, many approximation algorithms have been proposed. two types of best approximation algorithms for max sat were proposed by asano and williamson: one with best proven performance guarantee 0.7846 and the other with performance guarantee 0.8331 if the performance guarantee of the zwick's algorithm for max sat is, as conjectured. both algorithms are based on their sharpened analysis of goemans and williamson's lp-relaxation for max sat. in this paper, we present an improved analysis which is simpler than the previous analysis. furthermore, algorithms based on this, analysis will play a role as a better building block in designing an improved approximation algorithm for max sat. actually we, show an example that algorithms based on this analysis lead to approximation algorithms with performance guarantee 0.7877 and, conjectured performance guarantee 0.8353 which are slightly better than the best known corresponding performance guarantees, 0.7846 and 0.8331, respectively.
the structure and number of global roundings of a graph. given a connected weighted graph g = (v,e), we consider a hypergraph hg = (v, pg) corresponding to the set of all shortest paths in g. for a given real assignment a on v satisfying 0≤a(v)≤1, a global rounding α with respect to hg is a binary assignment satisfying that |σv∈fa(v)-α(v)| <1 for every f ∈ pg. we conjecture that there are at most |v| + 1 global roundings for hg, and also the set of global roundings is an affine independent set. we give several positive evidences for the conjecture.
interaction systems ii: the practice of optimal reductions. lamping''s optimal graph reduction technique for the lambda-calculus is generalized to a new class of higher order rewriting systems, called interaction systems. interaction systems provide a nice integration of the functional paradigm with a rich class of data structures (all inductive types), and some basic control flow constructs such as conditionals and (primitive or general) recursion. we describe a uniform and optimal implementation, in lamping''s style, for all these features. this work is the natural continuation of our previous paper "interaction systems i, the theory of optimal reductions", where we focused on the theoretical aspects of optimal reductions in is''s (family relation, labeling, extraction, an so on).
subtyping dependent types. the need for subtyping in type systems with dependent types has been realized for some years. but it is hard to prove that systems combining the two features have fundamental properties such as subject reduction. here we investigate a subtyping extension of the system λp, which is an abstract version of the type system of the edinburgh logical framework lf. by using an equivalent formulation, we establish some important properties of the new system λp6=, including subject reduction. our analysis culminates in a complete and terminating algorithm which establishes the decidability of type-checking. copyright 2001 elsevier science b.v.