waashk/dblp huggingface dataset:
scalable percolation search on complex networks. we introduce a scalable searching protocol for locating and retrieving content in random networks with heavy-tailed and in particular power-law (pl) degree distributions. the proposed algorithm is capable of finding any content in the network with probability one in time o(log n), with a total traffic that provably scales sub-linearly with the network size, n. unlike other proposed solutions, there is no need to assume that the network has multiple copies of contents; the protocol finds all contents reliably, even if every node in the network starts with a unique content. the scaling behavior of the size of the giant connected component of a random graph with heavy-tailed degree distributions under bond percolation is at the heart of our results. the percolation search algorithm can be directly applied to make unstructured peer-to-peer (p2p) networks, such as gnutella, limewire and other file-sharing systems (which naturally display heavy-tailed degree distributions and approximate scale-free network structures), scalable. for example, simulations of the protocol on the limewire crawl number 5 network [ripeanu et al., mapping the gnutella network: properties of large-scale peer-to-peer systems and implications for system design, ieee internet comput. j. 6 (1) (2002)], consisting of over 65,000 links and 10,000 nodes, shows that even for this snapshot network, the traffic can be reduced by a factor of at least 100, and yet achieve a hit-rate greater than 90%.
locating reaction with 2-categories. groupoidal relative pushouts (grpos) have recently been proposed by the authors as a new foundation for leifer and milner's approach to deriving labelled bisimulation congruences from reduction systems. in this paper, we develop the theory of grpos further, proving that well-known equivalences, other than bisimulation, are congruences. to demonstrate the type of category theoretic arguments which are inherent in the 2-categorical approach, we construct grpos in a category of 'bunches and wirings.' finally, we prove that the 2-categorical theory of grpos is a generalisation of the approaches based on milner's precategories and leifer's functorial reactive systems.
learning taxonomic relation by case-based reasoning. in this paper, we propose a learning method of minimal casebase to represent taxonomic relation in a tree-structured concept hierarchy. we firstly propose case-based taxonomic reasoning and show an upper bound of necessary positive cases and negative cases to represent a relation. then, we give a learning method of a minimal casebase with sampling and membership queries. we analyze this learning method by sample complexity and query complexity in the framework of pac learning.
approximation of boolean functions by combinatorial rectangles. this paper deals with the number of monochromatic combinatorial rectangles required to approximate a boolean function on a constant fraction of all inputs, where each rectangle may use its own partition of the input variables. the main result of the paper is that the number of rectangles required for the approximation of boolean functions in this model is very sensitive to the allowed error. there is an explicitly defined sequence of boolean functions fn on n variables such that fn, has rectangle approximations with a constant number of rectangles and one-sided error 1/3 + o(1) or two-sided error 1/4 + o(1), but, on the other hand, fn requires exponentially many rectangles if the error bounds are decreased by an arbitrarily small constant.as applications of this result, the following separation results for read-once branching programs are obtained. the functions from the main result require only linear size for nondeterministic read-once branching programs and randomized read-once branching programs with two-sided error 1/3 + o(1), while randomized read-once branching programs with constant two-sided error smaller than 1/3 and unambiguous nondeterministic read-once branching programs require exponential size.
quantum branching programs and space-bounded nonuniform quantum complexity. in this paper, the space complexity of non-uniform quantum algorithms is investigated using the model of quantum branching programs (qbps). in order to clarify the relationship between qbps and non-uniform quantum turing machines, simulations between these two models are presented which allow to transfer upper and lower bound results. exploiting additional insights about the connection between the running time and the precision of amplitudes, it is shown that non-uniform quantum turing machines with algebraic amplitudes and qbps with a suitable analogous set of amplitudes are equivalent in computational power if both models work with bounded or unbounded error. furthermore, quantum ordered binary decision diagrams (qobdds) are considered, which are restricted qbps that can be regarded as a non-uniform analog of one-way quantum finite automata. upper and lower bounds are proved that allow a classification of the computational power of qobdds in comparison to usual deterministic and randomized variants of the model. finally, an extension of qbps is proposed where the performed unitary operation may depend on the result of a previous measurement. a simulation of randomized bps by this generalized qbp model as well as exponential lower bounds for its ordered variant are presented.
improved shortest path algorithms for nearly acyclic graphs. dijkstra's algorithm solves the single-source shortest path problem on any directed graph in o(m + n log n) time when a fibonacci heap is used as the frontier set data structure. here n is the number of vertices and m is the number of edges in the graph. if the graph is nearly acyclic, other algorithms can achieve a time complexity lower than that of dijkstra's algorithm. abuaiadh and kingston gave a single-source shortest path algorithm for nearly acyclic graphs with o(m + n log t) time complexity, where the new parameter, t, is the number of delete-min operations performed in priority queue manipulation. if the graph is nearly acyclic, then t is expected to be small, and the algorithm out-performs dijkstra's algorithm. takaoka, using a different definition for acyclicity, gave an algorithm with o(m + n log k) time complexity. in this algorithm, the new parameter, k, is the maximum cardinality of the strongly connected components in the graph.the generalised single-source (gss) problem allows an initial distance to be defined at each vertex in the graph. decomposing a graph into r trees allows the gss problem to be solved within o(m + r logr) time. this paper presents a new all-pairs algorithm with a time complexity of o(mn + nr log r), where r is the number of acyclic parts resulting when the graph is decomposed into acyclic parts. the acyclic decomposition used is setwise unique and can be computed in o(mn) time. if the decomposition has been pre-calculated, then gss can be solved within o(m + r log r) time whenever edge-costs in the graph change. a second new all-pairs algorithm is presented, with o(mn + nr2) worst-case time complexity, where r is the number of vertices in a pre-calculated feedback vertex set for the nearly acyclic graph. for certain graphs, these new algorithms offer an improvement on the time complexity of the previous algorithms.
a hierarchy result for read-once branching programs with restricted parity nondeterminism. restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for boolean functions. in this paper (⊕, k)-branching programs and (∨, k)-branching programs are considered, i.e., branching programs starting with a ⊕- (or ∨-)node with a fan-out of k whose successors are k read-once branching programs. this model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. lower bound methods and hierarchy results for polynomial size (⊕, k)- and (∨, k)-branching programs with respect to k are presented.
a fast algorithm to generate necklaces with fixed content. we develop a fast algorithm for listing all necklaces with fixed content. by fixed content, we mean the number of occurrences of each alphabet symbol is fixed. initially, we construct a simple but inefficient algorithm by making some basic modifications to a recursive necklace generation algorithm. we then improve it by using two classic combinatorial optimization techniques. an analysis using straight forward bounding techniques is used to prove that the algorithm runs in constant amortized time.
oracles for vertex elimination orderings. by maintaining appropriate data structures, we develop constant-time transposition oracles that answer whether or not two adjacent vertices in a simple elimination ordering (seo) or a semiperfect elimination ordering (semipeo) can be swapped to produce a new seo or semipeo, respectively. combined with previous results regarding convex geometries and antimatroids, this allows us to list all seos of a strongly chordal graph and all semipeos of an hhda-free graph in gray code order. by applying a new amortized analysis we show that the algorithms run in constant amortized time.additionally, we provide a simple framework that can be used to exhaustively list the basic words for other antimatroids.
precise goal-independent abstract interpretation of constraint logic programs. we present a goal-independent abstract interpretation framework for constraint logic programs, and prove the sufficiency of a set of conditions for abstract domains to ensure that the analysis will never lose precision. along the way, we formally define constraint logic programming systems, give a formal semantics that is independent of the actual constraint domain and the details of the proof algorithm, and formally define the maximally precise abstraction of a constraint logic program.
topology matters: smoothed competitiveness of metrical task systems. borodin et al. (j. acm 39 (1992) 745) introduced metrical task systems, a framework to model a large class of online problems. metrical task systems can be described as follows. we are given a graph g = (v, e) with n nodes and a positive edge length λ(e) for every edge e ∈ e. an online algorithm resides in g and has to service a sequence of tasks that arrive online. a task τ specifies for each node v; ∈ v a request cost r (v) ∈ r0+ ∪ {∞}. if the algorithm resides in node u before the arrival of task τ, the cost to service task τ in node v is equal to the shortest path distance from u to v plus the request cost r(v). the objective is to service all tasks at minimum total cost. borodin et al. showed that every deterministic online algorithm has a competitive ratio of at least 2n - 1, independent of the underlying metric. moreover, they presented an online work function algorithm (wfa) that achieves this competitive ratio.we present a smoothed competitive analysis of wfa. that is, given an adversarial task sequence, we randomly perturb the request costs and analyze the competitive ratio of wfa on the perturbed sequence. here, we are mainly interested in the asymptotic behavior of wfa. our analysis reveals that the smoothed competitive ratio of wfa is much better than o(n) and that it depends on several topological parameters of the underlying graph g, such as the minimum edge length λmin, the maximum degree δ, the edge diameter emax, etc. for example, if the ratio between the maximum and the minimum edge length of g is bounded by a constant, the smoothed competitive ratio of wfa is o(emax (λmin/σ + log(δ))) and o(√nċ (λmin/sigma + log(δ))), where σ denotes the standard deviation of the smoothing distribution. that is, already for perturbations with σ= θ(λmin) the competitive ratio reduces to o(log(n)) on a clique and to o(√/n) on a line. furthermore, we provide lower bounds on the smoothed competitive ratio of any deterministic algorithm. we prove two general lower bounds that hold independently of the underlying metric. moreover, we show that our upper bounds are asymptotically tight for a large class of graphs.we also provide the first average case analysis of wfa. we prove that wfa has o(log(δ)) expected competitive ratio if the request costs are chosen randomly from an arbitrary non-increasing distribution with standard deviation σ = θ(λmin).
poset-valued sets or how to build models for linear logics. we describe a method for constructing models of linear logic based on the category of sets and relations. the resulting categories are non-degenerate in general; in particular they are not compact closed nor do they have biproducts. the construction is simple, lifting the structure of a poset to the new category. the underlying poset thus controls the structure of this category, and different posets give rise to differently-flavoured models. as a result, this technique allows the construction of models for both, intuitionistic or classical linear logic as desired. a number of well-known models, for example coherence spaces and hypercoherences, are instances of this method.
the correspondence between partial metrics and semivaluations. partial metrics, or the equivalent weightable quasi-metrics, have been introduced in matthews (proc. 8th summer conf. on general topology and applications; ann. new york acad. sci. 728 (1994) 183) as part of the study of the denotational semantics of data flow networks (theoret. comput. sci. 151 (1995) 195). the interest in valuations in connection to domain theory derives from e.g. jones and plotkin (lics '89, ieee computer society press, silver spring, md, 1998, pp. 186-195), jones (ph.d. thesis, university of edinburgh, 1989), edalat (lics'94, ieee computer society press, silver spring, md, 1994) and heckmann (fund. inform. 24(3) (1995) 259). connections between partial metrics and valuations have been discussed in the literature, e.g. o'neill (in: s. andima et al. (eds.), proc. 11th summer conf. on general topology and applications; ann. new york acad. sci. 806 (1997) 304), bukatin and scott (in: s. adian, a. nerode (eds.), logical foundations of computer science, lecture notes in computer science, vol. 1234, springer, berlin, 1997, pp. 33-43) and bukatin and shorina (in: m. nivat (ed.), foundations of software science and computation structures, lecture notes in computer science, vol. 1378, springer, berlin, 1998, pp. 125-139). in each case, partial metrics are generated from strictly increasing valuations.we analyze the precise relationship between these two notions. it is well known that characterizations of partial metrics in general are hard to obtain, as witnessed by the open characterization problems in the survey paper nonsymmetric topology (kúnzi (bolyai soc. math. stud. 4 (1993) 303). our approach to obtaining such a characterization involves the isolation of a "mathematically nice" class of spaces, which is sufficiently large to incorporate the quantitative domain theoretic examples involving partial metric spaces.for these purposes we focus on the class of quasi-metric semilattices. these structures, as will be illustrated, arise naturally in quantitative domain theory and include in particular the class of totally bounded scott domains discussed in smyth (in: g.m. reed, a.w. roscoe, r.f. wachter (ed.), topology and category theory in computer science, oxford university press, oxford, 1991, pp. 207-229), the baire quasi-metric spaces of (theoret. comput. sci. 151 (1995) 195), the complexity spaces of schellekens (in: proc. mfps 11, electronic notes in theoretical computer science, vol. i, elsevier, amsterdam, 1995, pp. 211-232) and the interval domain (proc. twelfth ann. ieee symp. on logic in computer science, ieee press, new york, 1997, pp. 248-257).we introduce the notion of a semivaluation, which generalizes the fruitful notion of a valuation on a lattice to the context of semilattices and establish a correspondence between partial metric semilattices and semivaluation spaces.
asm refinement and generalizations of forward simulation in data refinement: a comparison. in (j. universal comput. sci. 7 (2001) 952), we have formalized börger's refinement notion for abstract state machines (asms). the formalization was based on transition systems and verification conditions were expressed in dynamic logic.in this paper, the relation between asm refinement and data refinement is explored. data refinement expresses operations and verification conditions using relational calculus.we show how to bridge the gap between the different notations, and that forward simulation in the behavioral approach to data refinement can be viewed as a specific instance of asm refinement with 1:1 diagrams, where control structure is not refined.we also prove that two recent generalizations of data refinement, weak refinement and coupled refinement can be derived from asm refinement.
explaining updates by minimal sums. human reasoning about developments of the world involves always an assumption of inertia. we discuss two approaches for formalizing such an assumption, based on the concept of an explanation: (1) there is a general preference relation given on the set of all explanations and (2) there is a notion of a distance between models and explanations are preferred if their sum of distances is minimal. each distance dist naturally induces a preference relation dist. we show exactly under which conditions the converse is true as well and therefore both approaches are equivalent modulo these conditions. our main result is a general representation theorem in the spirit of kraus, lehmann and magidor. copyright 2001 elsevier science b.v.
theory of genetic algorithms ii: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling. we present a theoretical framework for an asymptotically converging, scaled genetic algorithm which uses an arbitrary-size alphabet and common scaled genetic operators. the alphabet can be interpreted as a set of equidistant real numbers and multiple-spot mutation performs a scalable compromise between pure random search and neighborhood-based change on the alphabet level. we discuss several versions of the crossover operator and their interplay with mutation. in particular, we consider uniform crossover and gene-lottery crossover which does not commute with mutation. the vose-liepins version of mutation-crossover is also integrated in our approach. in order to achieve convergence to global optima, the mutation rate and the crossover rate have to be annealed to zero in proper fashion, and unbounded, power-law scaled proportional fitness selection is used with logarithmic growth in the exponent. our analysis shows that using certain types of crossover operators and large population size allows for particularly slow annealing schedules for the crossover rate. in our discussion, we focus on the following three major aspects based upon contraction properties of the mutation and fitness selection operators: (i) the drive towards uniform populations in a genetic algorithm using standard operations, (ii) weak ergodicity of the inhomogeneous markov chain describing the probabilistic model for the scaled algorithm, (iii) convergence to globally optimal solutions. in particular, we remove two restrictions imposed in theorem 8.6 and remark 8.7 of (theoret. comput. sci. 259 (2001) 1) where a similar type of algorithm is considered as described here: mutation need not commute with crossover and the fitness function (which may come from a coevolutionary single species setting) need not have a single maximum.
tabular parsing and algebraic transformations. tabular parsing is described by means of two homomorphic algebras. in this setting, the parsing problem is described as the computation of the inverse image of an input string with respect to the homomorphism. tabulation is obtained by constructing a quotient of the first algebra and using a finite subalgebra of the second algebra. the valid parse items are the elements generated by the variable-free terms in the product of these two algebras. this yields an algebraic construction method for tabular algorithms. we demonstrate the method by constructing a tabular bottom-up head-corner algorithm for context-free grammars. we then use the algebraic description of this algorithm to construct a tabular algorithm for linear indexed grammars, using a correctness-preserving algebraic transformation. this transformation is a formalization of the idea of an efficient representation of the unbounded lig stacks that is stated only informally in previous constructions of lig algorithms. the main feature of this method is the modularity of the construction, by allowing simpler tabular algorithms to be reused for the construction of more complex ones.
axioms for real-time logics. this paper presents a complete axiomatization of two decidable propositional real-time linear temporal logics: event clock logic (eventclocktl) and metric interval temporal logic with past (metricintervaltl). the completeness proof consists of an effective proof building procedure for eventclocktl. from this result we obtain a complete axiomatization of metricintervaltl by providing axioms translating metricintervaltl formulae into eventclocktl formulae, the two logics being equally expressive. our proof is structured to yield axiomatizations also for interesting fragments of these logics, such as the linear temporal logic of the real numbers (tlr).
two optimal parallel algorithms on the commutation class of a word. the free partially commutative monoid m(a,θ) defined by a set of commutation relations θ on an alphabet a can be viewed as a model for concurrent computing: indeed, the independence or the simultaneity of two actions can be interpreted by the commutation of two letters that encode them. in this context, the commutation class cθ(w) of a word w of the free monoid a* plays a crucial role. the main results presented in this paper are the following: - a characterization of the minimal automaton aθ(w) for cθ(w) with the help of the new notion of θ-dissection. - a parallel algorithm which computes the minimal automaton aθ(w). this algorithm is optimal if the size of a is constant. - an optimal parallel algorithm for testing if a word belongs to the commutation class cθ(w).our approach differs completely from the methods (based on foata's normal form) used by cérin and petit (application de la théorie des traces à l'implantation et à la mesure d'algorithmes de distribution, thèse université paris 11, centre d'orsay, 1993; proc. 6th internat. parallel processing symp. (ipps), ieee press, new york, 1992, pp. 374-379; proc. mfcs'93, lecture notes in computer science, vol. 711, springer, berlin, 1993, pp. 332-341) for solving similar problems. under some assumptions the first algorithm achieves an optimal speedup. the second algorithm achieves also an optimal speedup and has a time complexity in o(log n) if the number of processors is in o(n) where n is the length of the word w, the total number of operations is in o(n) and does not depend on the size of the alphabet a as for the classical sequential algorithm.
extended admissibility. we give a new definition of admissible representations which allows to handle also non countably-based topological spaces in the framework of type-2 theory of effectivity. we prove that admissible representations δx, δy of topological spaces x,y have the desirable property that every partial function f :⊆ x → y is continuously realizable with respect to δx, δy if and only if f is sequentially continuous. furthermore, we characterize the class of the spaces having an admissible representation. many interesting operators creating new topological spaces from old ones are shown to preserve the property of having an admissible representation. in particular, the class of sequential spaces with admissible representations turns out to be cartesian-closed. thus, a reasonable computability theory is possible on important non countably-based spaces.