waashk/dblp huggingface dataset:
an algebraic model of observable properties in distributed systems. we propose orthomodular posets, algebraic models of quantum logic, as a formal tool in concurrency theory. we discuss their characteristics and study mutual relations with two other models of distributed systems: condition event net systems, a basic class of petri nets, and the transition systems modelling ce net system behaviour. central results are an adjointness situation among the three models and a strict relationship between fundamental notions in the different considered frameworks such as the relations of incompatibility and concurrency. furthermore, substructures of orthomodular posets, like boolean subalgebras or centres are interpreted, respectively, as state machine components of ce net systems or synchronization structures.
performance measure sensitive congruences for markovian process algebras. the modeling and analysis experience with process algebras has shown the necessity of extending them with priority, probabilistic internal/external choice, and time while preserving compositionality. the purpose of this paper is to make a further step by introducing a way to express performance measures, in order to allow the modeler to capture the qos metrics of interest. we show that the standard technique of expressing stationary and transient performance measures as weighted sums of state probabilities and transition frequencies can be imported in the process algebra framework. technically speaking, if we denote by n ∈ n the number of performance measures of interest, in this paper we define a family of extended markovian process algebras with generative master-reactive slaves synchronization mechanism called empagrn including probabilities, priorities, exponentially distributed durations, and sequences of rewards of length n. then we show that the markovian bisimulation equivalence ∼mbn is a congruence for empagrn which preserves the specified performance measures and we give a sound and complete axiomatization for finite empagrn terms. finally, we present a case study conducted with the software tool two towers in which we contrast the average performance of a selection of distributed algorithms for mutual exclusion modeled with empagrn.
a tutorial on empa: a theory of concurrent processes with nondeterminism, priorities, probabilities and time. we give an overview of empa, a process algebra for modeling and analyzing concurrent systems where nondeterminism, priorities, probabilities and time are present, aiming at a reasonable trade off between the expressive power of the calculus and the complexity of its underlying theory.
the complexity of computing the mcd-estimator. in modern statistics the robust estimation of parameters is a central problem, i.e., an estimation that is not or only slightly affected by outliers in the data. the minimum covariance determinant (mcd) estimator (j. amer. statist. assoc. 79 (1984) 871) is probably one of the most important robust estimators of location and scatter. the complexity of computing the mcd, however, was unknown and generally thought to be exponential even if the dimensionality of the data is fixed.here we present a polynomial time algorithm for mcd for fixed dimension of the data. in contrast we show that computing the mcd-estimator is np-hard if the dimension varies.
primality test for numbers m with a large power of 5 dividing m-1. the quintic reciprocity law is used to produce an algorithm, that runs in polynomial time, and that determines the primality of numbers m, such that m4 - 1, is divisible by a power of 5 which is larger that √m, provided that a small prime p, p ≡ 1 (mod 5) is given, such that m, is not a fifth power modulo p. the same test equations are used for all such m.a sufficiency test, together with its probability of succeeding in determining primality is given when the condition on m modulo p is omitted.
growth of repetition-free words -- a review. this survey reviews recent results on repetitions in words, with emphasis on the estimations for the number of repetition-free words.
shuffle factorization is unique. we prove that, given a finite set of words s, there exists at most one (normalized) multiset p such that s is the shuffle of the words in p. the multiset p is effectively computable.
operations preserving regular languages. given a strictly increasing sequence s of non-negative integers, filtering a word a0a1.... an by s consists in deleting the letters ai such that i is not in the set {s0,s1,...}. by a natural generalization, denote by l[s], where l is a language, the set of all words of l filtered by s. the filtering problem is to characterize the filters s such that, for every regular language l, l[s] is regular. in this paper, the filtering problem is solved, and a unified approach is provided to solve similar questions, including the removal problem considered by seiferas and mcnaughton. our approach relies on a detailed study of various residual notions, notably residually ultimately periodic sequences and residually rational transductions.
mixed languages. let t = a ∪ b ∪ c be an alphabet that is partitioned into three subalphabets. the mixing product of a word g over a ∪ b and of a word d over a ∪ c is the set of words w over t such that its projection onto a ∪ b gives g and its projection onto a ∪ c gives d.let r be a regular language over t such that xbcy is in r if and only if xcby is in r for any two letters b in b and c in c. in other words, r is commutative over b and c. is this property "structural" in the sense that r can then be obtained as a mixing product of a regular language over a ∪ b and of a regular language over a ∪ c?this question has a rather easy answer, but there are many cases where the answer is negative. a more interesting question is whether r can be represented as a finite union of mixed products of regular languages. for the moment, we do not have an answer to this question. however, we prove that it is decidable whether, for a given k, the language r is a union of at most k mixed products of regular languages.
coding rotations on intervals. we show that the coding of a rotation by on m intervals can be recoded over m sturmian words of angle.
smooth words over arbitrary alphabets. smooth infinite words over ∑ = {1, 2} are connected to the kolakoski word k = 221121 ..., defined as the fixpoint of the function δ that counts the length of the runs of 1's and 2's. in this paper we extend the notion of smooth words to arbitrary alphabets and study some of their combinatorial properties. using the run-length encoding δ, every word is represented by a word obtained from the iterations of δ. in particular we provide a new representation of the infinite fibonacci word f as an eventually periodic word. on the other hand, the thue-morse word is represented by a finite one.
balance properties of multi-dimensional words. a word u is called 1-balanced if for any two factors v and w of u of equal length, we have 1|v|i|w|i1 for each letter i, where |v|i denotes the number of occurrences of i in the factor v. the aim of this paper is to extend the notion of balance to multi-dimensional words. we first characterize all 1-balanced words on &zn. in particular, we prove they are fully periodic for n>1. we then give a quantitative measure of non-balancedness for some words on &z2 with irrational density, including two-dimensional sturmian words.
lattices and multi-dimensional words. in the present paper we develop a formalism to generate multi-dimensional words using lattices which generalizes the construction of real numbers (one-dimensional words) from a sequence of partial quotients using continued fractions. the construction was introduced in a special case by simpson and tijdeman in order to derive a multi-dimensional generalization of the theorem of fine and wilf. we show that the produced multi-dimensional words are intrinsically connected with k-dimensional sturmian words.
bounding the firing synchronization problem on a ring. in this paper we improve the upper and lower bounds on the complexity of solutions to the firing synchronization problem on a ring. in this variant of the firing synchronization problem the goal is to synchronize a ring of identical finite automata. initially, all automata are in the same state except for one automaton that is designated as the initiator for the synchronization. the goal is to define the set of states and the transition function for the automata so that all machines enter a special fire state for the first time and simultaneously during the final round of the computation. in our work we present two solutions to the ring firing synchronization problem, an 8-state minimal-time solution and a 6-state non-minimal-time solution. both solutions use fewer states than the previous best-known minimal-time automaton, a 16-state solution due to culik. we also give the first lower bounds on the number of states needed for solutions to the ring firing synchronization problem. we show that there is no 3-state solution and no 4-state, symmetric, minimal-time solution for the ring.
on the number of occurrences of a symbol in words of regular languages. we study the random variable yn representing the number of occurrences of a symbol a in a word of length n chosen at random in a regular language l ⊆ {a, b}*, where the random choice is defined via a non-negative rational formal series r of support l. assuming that the transition matrix associated with r is primitive we obtain asymptotic estimates for the mean value and the variance of yn and present a central limit theorem for its distribution. under a further condition on such a matrix, we also derive an asymptotic approximation of the discrete fourier transform of yn, that allows to prove a local limit theorem for yn. further consequences of our analysis concern the growth of the coefficients in rational formal series; in particular, it turns out that, for a wide class of regular languages l, the maximum number of words of length n in l having the same number of occurrences of a given symbol is of the order of growth λn/√n, for some constant λ>1.
small size quantum automata recognizing some regular languages. given a class {pα | α ∈ i} of stochastic events induced by m-state 1-way quantum finite automata (1qfa) on alphabet σ, we investigate the size (number of states) of 1qfa's that δ-approximate a convex linear combination of {pα | α ∈ i}, and we apply the results to the synthesis of small size 1qfa's. we obtain: • an o((md/δ3) log2(d/δ2)) general size bound, where d is the vapnik dimension of {pα(w) | w ∈ σ*}. • for commutative n-periodic events p on σ with |σ| = h, we prove an o((h log n/δ2)) size bound for inducing a δ-approximation of ½ + ½ p whenever ||f(p)||1 ≤nh, where f(p) is the discrete fourier transform of (the vector p associated with) p. • if the characteristic function χl of an n-periodic unary language l satisfies ||f(χl))||1 ≤ n, then l is recognized with isolated cut-point by a 1qfa with o(log n) states. vice versa, if l is recognized with isolated cut-point by a 1qfa with o(log n) state, then ||f(χl))||1 = o(n log n).
some formal tools for analyzing quantum automata. results in the area of compact monoids and groups are useful in the analysis of quantum automata (lqfa's). in this paper: (1) we settle isolated cut point rabin's theorem in the context of compact monoids, and we prove a lower bound on the state complexity of lqfa's accepting regular languages. (2) we use a method pointed out by blondel et al. [decidable and undecidable problems about quantum automata, technical report rr2003-24, lip, ens lyon, 2003] based on compact groups theory to design an algorithm for testing whether a k-tuple of lqfa's is a classifier of words in σ*; this problem turns out to be undecidable if the completeness of the classifier is required. (3) in the unary case, we give an exponential time algorithm for computing the descriptional complexity of periodic languages. moreover, we present a probabilistic method to construct lqfa's exponentially succinct in the period and polynomially succinct in the inverse of the bounded error.
gemmating p systems: collapsing hierarchies. we continue the analysis of p systems with gemmation of mobile membranes. we solve an open problem from besozzi et al. (proc. italian conf. on theoretical computer science 2001, lecture notes in computer science, vol. 2202, springer, berlin, 2001, pp. 136-153), showing that the hierarchy on the number of membranes collapses: systems with eight membranes characterize the recursively enumerable languages (seven membranes are enough in the case of extended systems). we also prove that p systems, which use only gemmation, but neither classical rewriting rules nor in/out communications, can generate the same family of languages. in this case, the hierarchy on the number of membranes collapses to level nine.
proof-carrying code from certified abstract interpretation and fixpoint compression. proof-carrying code (pcc) is a technique for downloading mobile code on a host machine while ensuring that the code adheres to the host's safety policy. we show how certified abstract interpretation can be used to build a pcc architecture where the code producer can produce program certificates automatically. code consumers use proof checkers derived from certified analysers to check certificates. proof checkers carry their own correctness proofs and accepting a new proof checker amounts to type checking the checker in coq. certificates take the form of strategies for reconstructing a fixpoint and are kept small due to a technique for fixpoint compression. the pcc architecture has been implemented and evaluated experimentally on a byte code language for which we have designed an interval analysis that allows to generate certificates ascertaining that no array-out-of-bounds accesses will occur.
how to analyse evolutionary algorithms. many variants of evolutionary algorithms have been designed and applied. the experimental knowledge is immense. the rigorous analysis of evolutionary algorithms is difficult, but such a theory can help to understand, design, and teach evolutionary algorithms. in this survey, first the history of attempts to analyse evolutionary algorithms is described and then new methods for continuous as well as discrete search spaces are presented and discussed.
the enumerability of p collapses p to nc. we show that one cannot rule out even a single possibility for the value of an arithmetic circuit on a given input using an nc algorithm, unless p collapses to nc (i.e., unless all problems with polynomial-time sequential solutions can be efficiently parallelized). in other words, excluding any possible solution in this case is as hard as actually finding the solution. the result is robust with respect to nc algorithms that err (i.e., exclude the correct value) with small probability. we also show that p collapses all the way down to nc1 when the characteristic of the field that the problem is over is sufficiently large (but in this case under a stronger elimination hypothesis that depends on the characteristic).
edge-isoperimetric problems for cartesian powers of regular graphs. we consider an edge-isoperimetric problem (eip) on the cartesian powers of graphs. one of our objectives is to extend the list of graphs for whose cartesian powers the lexicographic order provides nested solutions for the eip. we present several new classes of such graphs that include as special cases all presently known graphs with this property. our new results are applied to derive best possible edge-isoperimetric inequalities for the cartesian powers of arbitrary regular, resp. regular bipartite, graphs with a high density.
new spectral lower bounds on the bisection width of graphs. the communication overhead is a major bottleneck for the execution of a process graph on a parallel computer system. in the case of two processors, the minimization of the communication can be modeled using the graph bisection problem. the spectral lower bound of λ2|v|/4 for the bisection width of a graph is widely known. the bisection width is equal to λ2|v|/4 iff all vertices are incident to λ2/2 cut edges in every optimal bisection.we present a new method of obtaining tighter lower bounds on the bisection width. this method makes use of the level structure defined by the bisection. we define some global expansion properties and we show that the spectral lower bound increases with this global expansion. under certain conditions we obtain a lower bound depending on λ2β|v with ½ < β ≤ 1. we also present examples of graphs for which our new bounds are tight up to a constant factor. as a by-product, we derive new lower bounds for the bisection widths of 3- and 4-regular ramanujan graphs.
a semantics for web services authentication. we consider the problem of specifying and verifying cryptographic security protocols for xml web services. the security specification ws-security describes a range of xml security elements, such as username tokens, public-key certificates, and digital signatures, amounting to a flexible vocabulary for expressing protocols. to describe the syntax of these elements, we extend the usual xml data model with symbolic representations of cryptographic values. we use predicates on this data model to describe the semantics of security elements and of sample protocols distributed with the microsoft wse implementation of ws-security. by embedding our data model within abadi and fournet's applied pi calculus, we formulate and prove security properties with respect to the standard dolev-yao threat model. moreover, we informally discuss issues not addressed by the formal model. to the best of our knowledge, this is the first approach to the specification and verification of security protocols based on a faithful account of the xml wire format.
observational logic, constructor-based logic, and their duality. observability and reachability are important concepts for formal software development. while observability concepts are used to specify the required observable behavior of a program or system, teachability concepts are used to describe the underlying data in terms of datatype constructors. in this paper we first reconsider the observational logic institution which provides a logical framework for dealing with observabifity. then we develop in a completely analogous way the constructor-based logic institution which formalizes a novel treatment of reachability. both institutions are tailored to capture the semantically correct realizations of a specification from either the observational or the reachability point of view. we show that there is a methodological and even formal duality between both frameworks. in particular, we establish a correspondence between observer operations and datatype constructors, observational and constructor-based algebras, fully abstract and reachable algebras, and observational and inductive consequences of specifications. the formal duality between the observability and reachability concepts is established in a category-theoretic setting.
palindrome recognition using a multidimensional tape. the problem of palindrome recognition using a turing machine with one multidimensional tape is proved to, require θ(n2/log n) time.
finding hidden independent sets in interval graphs. we design efficient competitive algorithms for discovering hidden information using few queries. specifically, consider a game in a given set of intervals (and their implied interval graph g) in which our goal is to discover an (unknown) independent set x by making the fewest queries of the form "is point p covered by an interval in x?" our interest in this problem stems from two applications: experimental gene discovery with pcr technology and the game of battleship (in a 1-dimensional setting). we provide adaptive algorithms for both the verification scenario (given an independent set, is it x?) and the discovery scenario (find x without any information). under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.
global convergence for evolution strategies in spherical problems: some simple proofs and difficulties. this paper presents simple proofs for the global convergence of evolution strategies in spherical problems. we investigate convergence properties for both adaptive and self-adaptive strategies. regarding adaptive strategies, the convergence rates are computed explicitly and compared with the results obtained in the so-called "rate-of-progress" theory. regarding self-adaptive strategies, the computation is conditional to the knowledge of a specific induced markov chain. an explicit example of chaotic behavior illustrates the complexity in dealing with such chains. in addition to these proofs, this work outlines a number of difficulties in dealing with evolution strategies.
lyndon words and shuffle algebras for generating the coloured multiple zeta values relations tables. we study here the coloured multiple zeta values, obtained by extending the usual notion of the multiple zeta values by adding roots of unity. we state their main combinatorial properties. and we give, as a result, a maple algorithm which generates the relations table between these values.
quantum computing without entanglement. it is generally believed that entanglement is essential for quantum computing. we present here a few simple examples in which quantum computing without entanglement is better than anything classically achievable, in terms of the reliability of the outcome after a fixed number of oracle calls. using a separable (that is, unentangled) state, we show that the deutsch-jozsa problem and the simon problem can be solved more reliably by a quantum computer than by the best possible classical algorithm, even probabilistic. we conclude that: (a) entanglement is not essential for quantum computing; and (b) some advantage of quantum algorithms over classical algorithms persists even when the quantum state contains an arbitrarily small amount of information--that is, even when the state is arbitrarily close to being totally mixed.
a survey on tree edit distance and related problems. we survey the problem of comparing labeled trees based on simple local operations of deleting, inserting, and relabeling nodes. these operations lead to the tree edit distance, alignment distance, and inclusion problem. for each problem we review the results available and present, in detail, one or more of the central algorithms for solving the problem.
bernstein-bezoutian matrices. several computational and structural properties of bezoutian matrices expressed with respect to the bernstein polynomial basis are shown. the exploitation of such properties allows the design of fast algorithms for the solution of bernstein-bezoutian linear systems without never making use of potentially ill-conditioned reductions to the monomial basis. in particular, we devise an algorithm for the computation of the greatest common divisor (gcd) of two polynomials in bernstein form. a series of numerical tests are reported and discussed, which indicate that bernstein-bezoutian matrices are much less sensitive to perturbations of the coefficients of the input polynomials compared to other commonly used resultant matrices generated after having performed the explicit conversion between the bernstein and the power basis.
theoretical foundations of dynamic program slicing. this paper presents a theory of dynamic slicing, which reveals that the relationship between static and dynamic slicing is more subtle than previously thought. the definitions of dynamic slicing are formulated in terms of the projection theory of slicing. this shows that existing forms of dynamic slicing contain three orthogonal dimensions in their slicing criteria and allows for a lattice-theoretic study of the subsumption relationship between these dimensions and their relationship to static slicing formulations.