waashk/dblp huggingface dataset:
formal and incremental construction of distributed algorithms: on the distributed reference counting algorithm. the development of distributed algorithms and, more generally, distributed systems, is a complex, delicate and challenging process. refinement techniques of (system) models improve the process by using a proof assistant, and by applying a design methodology aimed at starting from the most abstract model and leading, in an incremental way, to the most concrete model, for producing a distributed solution. we show, using the distributed reference counting (drc) problem as our study, how models can be produced in an elegant and progressive way, thanks to the refinement and how the final distributed algorithm is built starting from these models. the development is carried out within the framework of the event b method and models are validated with a proof assistant.
two-level languages for program optimization. two-level languages incorporate binding time information inside types, that is, whether a piece of code is completely known at compile-time, or needs some more inputs and can be evaluated only at run-time. we consider the use of 2-level languages in the framework of partial evaluation, and use a 2-level version of the simply typed lambda calculus with recursion. we give an operational semantics, an equational theory and a denotational semantics, that give an account of the distinction between compilation and execution phases. an adequacy theorem is given to relate the two semantics, showing in particular how they agree on non-termination at compile time. we finally give a more refined model using functor categories.
program logic and equivalence in the presence of garbage collection. it is generally thought that reasoning about programs in memory safe, garbage collected languages is much easier than in languages where the programmer has more explicit control over memory. paradoxically, existing program logics are based on a low-level view of storage that is sensitive to the presence or absence of unreachable cells, and reynolds has pointed out that the hoare triples derivable in these logics are even incompatible with garbage collection. we present a study of a small language whose operational semantics includes a rule for reclaiming garbage. our main results include an analysis of propositions that are garbage insensitive, and full abstraction results connecting partial and total correctness to two natural notions of observational equivalence between programs.
compiling dyadic first-order specifications into map algebra. two techniques are designed for eliminating quantifiers from an existentially quantified conjunction of dyadic literals, in terms of the operators o, ∩, and -1 of the tarski-chin-givant formalism of relations. the use of such techniques is illustrated through increasingly challenging examples, and their algorithmic complexity is assessed.
axiomatization of frequent itemsets. mining association rules is very popular in the data mining community. most algorithms designed for finding association rules start with searching for frequent itemsets. typically, in these algorithms, counting phases and pruning phases are interleaved. in the counting phase, partial information about the frequencies of selected itemsets is gathered. in the pruning phase as much as possible of the search space is pruned, based on the counting information. we introduce frequent set expressions to represent (possible partial) information acquired in the counting phase. a frequent set expression is a pair containing an itemset and a fraction that is a lower bound on the actual frequency of the itemset. a system of frequent sets is a collection of such pairs. we give an axiomatization for those systems that are complete in the sense that they explicitly contain all information they logically imply. every system of frequent sets has a unique completion that actually represents all knowledge that can be derived. we also study sparse systems, in which not for every frequent set an expression is given. furthermore, we explore the links with probabilistic logics.
checkpointing with mutable checkpoints. there are two approaches to reduce the overhead associated with coordinated checkpointing: first is to minimize the number of synchronization messages and the number of checkpoints; the other is to make the checkpointing process non-blocking. in our previous work (ieee parallel distributed systems 9 (12) (1998) 1213), we proved that there does not exist a nonblocking algorithm which forces only a minimum number of processes to take their checkpoints. in this paper, we present a min-process algorithm which relaxes the non-blocking condition while tries to minimize the blocking time, and a non-blocking algorithm which relaxes the min-process condition while minimizing the number of checkpoints saved on the stable storage. the proposed non-blocking algorithm is based on the concept of "mutable checkpoint", which is neither a tentative checkpoint nor a permanent checkpoint. based on mutable checkpoints, our nonblocking algorithm avoids the avalanche effect and forces only a minimum number of processes to take their checkpoints on the stable storage.
combinatorial optimization algorithms for radio network planning. this paper uses a realistic problem taken from the telecommunication world as the basis for comparing different combinatorial optimization algorithms. the problem recalls the minimum hitting set problem, and is solved with greedy-like, darwinism and genetic algorithms. these three paradigms are described and analyzed with emphasis on the darwinism approach, which is based on the computation of &egr;-nets.
some properties of the factors of sturmian sequences. in this paper, we introduce the singular words of sturmian sequences, which play an important role in studying the properties of the factors of sturmian sequence. we also completely determine the powers of the factors, the overlaps of the factors and the structure of the palindromes of the factors.
splittable traffic partition in wdm/sonet rings to minimize sonet adms. sonet adms are the dominant cost factor in the wdm/sonet rings. recently several articles (belvaux et al., european j. oper. res. 108 (1) (1998) 26-35; clinescu and wan, traffic partition in wdm/sonet rings to minimize sonet adms, submitted for publication; gerstel et al., proc. ieee infocom'98, vol. 1, pp. 94-101; liu et al., proc. infocom, vol. 2, 2000, pp.~1020-1025; sutter et al., oper. res. 46 (5) (1998) 719-728) proposed a number of heuristics for traffic partition so as to use as few sonet adms as possible. most of these heuristics assumes wavelength-continuity, i.e., the same wavelength is allocated on all of the links in the path established for a traffic stream. it was first observed and argued by gerstel et al. that the number of adms can be potentially reduced by allowing a traffic stream to be locally transferred from one adm in a wavelength to another adm in a different wavelength at any intermediate node, in other words, the traffic streams are splittable. in this paper, we study two variations of this minimum adm problem with splittable traffic streams: all traffic streams have prespecified routings, and all traffic streams have no prespecified routings respectively. both variations are shown to be np-hard. for the former variation, a heuristic with approximation ratio at most 5/4 is proposed. for the latter variation, a similar heuristic with approximation ratio 3/2 is proposed.
a characterization of c.e. random reals. a real α is computably enumerable if it is the limit of a computable, increasing, converging sequence of rationals. a real α is random if its binary expansion is a random sequence. our aim is to offer a self-contained proof, based on the papers (calude et al., in: m. morvan, c. meinel, d. krob (eds.), proc. 15th symp. on theoretical aspects of computer science, paris, springer, berlin, 1998, pp. 596-606; chaitin, j. assoc. comput. mach. 22 (1975) 329; slaman, manuscript, 14 december 1998, 2 pp.; solovay, unpublished manuscript, ibm thomas j. watson research center, yorktown heights, new york, may 1975, 215 pp.), of the following theorem: a real is c.e. and random if and only if it is a chaitin&ohgr; real, i.e., the halting probability of some universal self-delimiting turing machine.
on the number of inductively minimal geometries. we count the number of inductively minimal geometries for any given rank by exhibiting a correspondence between the inductively minimal geometries of rank n and the trees with n + 1vertices. the proof of this correspondence uses the van rooij-wilf characterization of line graphs(see [11]).
edge coloring of bipartite graphs with constraints. a classical result from graph theory states that the edges of an l-regular bipartite graph can be colored using exactly l colors so that edges that share an endpoint are assigned different colors. in this paper, we study two constrained versions of the bipartite edge coloring problem. some of the edges adjacent to a specific pair of opposite vertices of an l-regular bipartite graph are already colored with s colors that appear only on one edge (single colors) and d colors that appear on two edges (double colors). we show that the rest of the edges can be colored using at most max{min{l+d,3l/2},l+(s+d)/2} total colors. we also show that this bound is tight by constructing instances in which max{min{l+d,3l/2},l+(s+d)/2} colors are indeed necessary. - some of the edges of an l-regular bipartite graph are already colored with s colors that appear only on one edge. we show that the rest of the edges can be colored using at most max{l+s/2,s} total colors. we also show that this bound is tight by constructing instances in which max{l+s/2,s} total colors are necessary.
streams and strings in formal proofs. streams are acyclic directed subgraphs of the logical flow graph of a proof representing bundles of paths with the same origin and the same end. the notion of stream is used to describe the evolution of proofs during cut-elimination in purely algebraic terms. the algebraic and combinatorial properties of flow graphs emerging from our analysis serve to elucidate logical phenomena. however, the full logical significance of the combinatorics, e.g. the absence of certain patterns within flow graphs, remains unclear.
on the size complexity of hybrid networks of evolutionary processors. the goal of this paper is twofold. firstly, to survey in a systematic and uniform way the main results regarding the size descriptional complexity measures of hybrid networks of evolutionary processors as generating devices. secondly, we improve some results about a size measure, prove that it is connected, and discuss the possibility of computing this measure for regular and context-free languages. we also briefly present a few np-complete problems and recall how they can be solved in linear time by accepting networks of evolutionary processors with linearly bounded resources (nodes, rules, symbols). finally, the size complexity of accepting hybrid networks of evolutionary processors recognizing all np languages in polynomial time is briefly discussed.
functional labels and syntactic entropy on dna strings and proteins. the dna of a cell is an object which admits a simple mathematical description and a convenient representation in a computer (it is given by an easily manipulatable list, a finite sequence in four letters typically of length between one million and 10 billions). in contrast to this, there is no simple way of describing the cell neither statically and even less temporally (dynamically). we shall indicate here a possible formalism of combinatorial and numerical (entropic) structures on spaces of sequences which reflect, up to some degree, the organization and functions of dna and proteins.
designing small keyboards is hard. we study the problem of placing symbols of an alphabet onto the minimum number of keys of a small keyboard so that any word of a given dictionary can be recognized univoquely only by looking at the corresponding sequence of keys. this problem is motivated by the design of small keyboards for mobile devices. we show that the problem is hard in general, and np-complete even if we only wish to decide whether two keys are sufficient. we also consider two variants of the problem. in the first one, symbols on a key must be contiguous in an ordered alphabet. in the second variant, a well-chosen measure of ambiguity in the recognition of the words is minimized given the number of keys. hardness and approximability results are given.
a coinductive completeness proof for the equivalence of recursive types. we prove that the equivalence of recursive types induced by the equality of their infinite unfoldings coincides with the equality of their interpretations as closures over the -model p.
a new proof-theoretic proof of the independence of kirby-paris' hydra theorem. a new proof is given for the independence of the termination of kirby-paris' hydra game from peano arithmetic by showing that it is strong enough to entail the termination of gentzen's reduction strategy for proof figures via an appropriate translation from derivations to hydras.
searching in random partially ordered sets. we consider the problem of searching for a given element in a partially ordered set. more precisely, we address the problem of computing efficiently near-optimal search strategies for typical partial orders under two classical models for random partial orders, the random graph model and the uniform model.we shall show that the problem of determining an optimal strategy is np-hard, but there are simple, fast algorithms able to produce near-optimal search strategies for typical partial orders under the two models of random partial orders that we consider. we present a (1 + o(1))- approximation algorithm for typical partial orders under the random graph model (constant p) and present a 6.34-approximation algorithm for typical partial orders under the uniform model. both algorithms run in polynomial time.
on the simulation of quantum turing machines. in this article we shall review several basic definitions and results regarding quantum computation. in particular, after defining quantum turing machines and networks the paper contains an exposition on continued fractions and on errors in quantum networks. the topic of simulation of quantum turing machines by means of obvious computation is introduced. we give a full discussion of the simulation of multitape quantum turing machines in a slight generalization of the class introduced by bernstein and vazirani. as main result we show that the fisher-pippenger technique can be used to give an o(tlogt) simulation of a multi-tape quantum turing machine by another belonging to the extended bernstein and vazirani class. this result, even if regarding a slightly restricted class of quantum turing machines improves the simulation results currently known in the literature.
semiperiodic words and root-conjugacy. a factor u of a word w is called right special if there exist two distinct letters a and b such that both ua and ub are factors of w. left special factors are defined symmetrically. by rw (resp. lw) we denote the minimal natural number such that there is no right (resp. left) special factor of w of length rw (resp. lw). moreover, hw (resp. kw) denotes the length of the shortest prefix (resp. suffix) which cannot be extended on the left (resp. right) in w. the parameters rw, lw, hw, and kw give interesting information on the structure of the word w. we consider the class of all finite words w such that rw > hw. these words are called semiperiodic. any periodic word is semiperiodic, whereas the converse is not generally true. several characterizations of semiperiodic words can be given. in particular, a word w is semiperiodic if and only if it has a period p ≤ |w| - rw. a further characterization of semiperiodic words relates with their infinite extensions. from this characterization one derives the following result, deeply related to the theorem of fine and wilf: if w is a (semiperiodic) word having two periods p,q ≤ |w| - rw, then also d = gcd(p,q) is a period of w. the root rw of a word w is its prefix whose length is equal to the minimal period of w. two words u and v are root-conjugate if their roots ru and rv are conjugate. one of the main results of the paper is the following. let w be a semiperiodic word. a word v has the same set of factors of length 1 +rw of w if and only if v is semiperiodic and root-conjugate with w. some applications and extensions of this result are proved.
completions in measure of languages and related combinatorial problems. we consider measures of languages induced by bernoulli distributions on the letters of a given alphabet. of particular interest are languages having a measure equal to 1 with respect to all positive bernoulli distributions (bernoulli sets). the main object of the paper is to study conditions ensuring that a given language has a finite bernoulli completion, i.e., it is included in a finite bernoulli set. some characterizations of languages having finite bernoulli completions are given. in the case of a two-letter alphabet it is shown that one can decide whether a finite language has a finite bernoulli completion or not. moreover, any finite code over a two-letter alphabet has a finite bernoulli completion. finally, we prove that two finite languages have the same measure with respect to all bernoulli distributions if and only if each of the two languages can be obtained from the other by using a finite number of times three suitable measure-invariant transformations.
codes of central sturmian words. a central sturmian word, or simply central word, is a word having two coprime periods p and q and length equal to p + q - 2. we consider sets of central words which are codes. some general properties of central codes are shown. in particular, we prove that a non-trivial maximal central code is infinite. moreover, it is not maximal as a code. a central code is called prefix central code if it is a prefix code. we prove that a central code is a prefix (resp., maximal prefix) central code if and only if the set of its 'generating words' is a prefix (resp., maximal prefix) code. a suitable arithmetization of the theory is obtained by considering the bijection θ, called ratio of periods, from the set of all central words to the set of all positive irreducible fractions defined as: θ(ε) = 1/1 and θ(w) = p/q (resp., θ(w) = q/p) if w begins with the letter a (resp., letter b), p is the minimal period of w, and q = |w| - p + 2. we prove that a central code x is prefix (resp., maximal prefix) if and only if θ(x) is an independent (resp., independent and full) set of fractions. finally, two interesting classes of prefix central codes are considered. one is the class of farey codes which are naturally associated with the farey series; we prove that farey codes are maximal prefix central codes. the other is given by uniform central codes. a noteworthy property related to the number of occurrences of the letter a in the words of a maximal uniform central code is proved.
fault-diagnosis of grid structures. the problem of fault diagnosis in grid-connected systems is considered. a diagnosis algorithm, called dags and based on the pmc model, is presented. dags provides a diagnosis which is shown to be correct, although possibly incomplete, if the cardinality of the actual fault set is below a bound tσ, dependent of the actual syndrome σ. a bound t independent of σ is also derived by a worst-case analysis covering the cases of triangular, square, hexagonal and octagonal grids. t is shown to be θ(n2/3), where n is the size of the system, for all the grids considered.
predictive learning models for concept drift. concept drift means that the concept about which data is obtained may shift from time to time, each time after some minimum permanence. except for this minimum permanence, the concept shifts may not have to satisfy any further requirements and may occur infinitely often. within this work is studied to what extent it is still possible to predict or learn values for a data sequence produced by drifting concepts. various ways to measure the quality of such predictions, including martingale betting strategies and density and frequency of correctness, are introduced and compared with one another. for each of these measures of prediction quality, for some interesting concrete classes, (nearly) optimal bounds on permanence for attaining learnability are established. the concrete classes, from which the drifting concepts are selected, include regular languages accepted by finite automata of bounded size, polynomials of bounded degree, and sequences defined by recurrence relations of bounded size. some important, restricted cases of drifts are also studied, for example, the case where the intervals of permanence are computable. in the case where the concepts shift only among finitely many possibilities from certain infinite, arguably practical classes, the learning algorithms can be considerably improved. copyright 2001 elsevier science b.v. all rights reserved.
synthesizing noise-tolerant language learners. an index for an r.e. class of languages (by definition) generates a sequence of grammars defining the class. an index for an indexed family of languages (by definition) generates a sequence of decision procedures defining the family. f. stephen's model of noisy data is empoloyed, in which, roughly, correct data crops up infintely often, and incorrect data only finitely often. studied, then, is the synthesis from indices for r.e. classes and for indexed families of languages of various kinds of noise-tolerant language-learners for the corresponding classes or families indexed. many positive results, as well as some negative results, are presented regarding the existence of such synthesizers. the proofs of most of the positive resutls yield, as pleasant corollaries, strict subset-principle or tell-tale style characterization for the noise-tolerant learn-ability of the corresponding classes or families indexed.
control structures in hypothesis spaces: the influence on learning. in any learnability setting, hypotheses are conjectured from some hypothesis space. studied herein are the influence on learnability of the presence or absence of certain control structures in the hypothesis space. first presented are control structure characterizations of some rather specific but illustrative learnability results. the presence of these control structures is thereby shown essential to maintain full learning power. then presented are the main theorems. each of these non-trivially characterizes the invariance of a learning class over hypothesis space v and the presence of a particular projection control structure, called proj, in v as: v has suitable instances of all denotational control structures. in a sense, then, proj epitomizes the control structures whose presence need not help and whose absence need not hinder learning power.
examples of undecidable problems for 2-generator matrix semigroups. examples of undecidable problems for 2-generator matrix semigroups
random generation of dfas. this document gives a generalization on the alphabet size of the method that is described in nicaud's thesis for randomly generating complete dfas. first, we recall some properties of m-ary trees and we give a bijection between the set of m-ary trees and the set r(m, n) of generalized tuples. we show that this bijection can be built on any total prefix order on σ*, then we give the relations that exist between the elements of r(m,n) and complete dfas built on an alphabet of size greater than 2. we give algorithms that allow us to randomly generate accessible complete dfas. finally, we provide experimental results that show that most of the accessible complete dfas built on an alphabet of size greater than 2 are minimal.