waashk/dblp huggingface dataset:
on the limits of cache-oblivious rational permutations. permuting a vector is a fundamental primitive which arises in many applications. in particular, rational permutations, which are defined by permutations of the bits of the binary representations of the vector indices, are widely used. matrix transposition and bit-reversal are notable examples of rational permutations. in this paper we contribute a number of results regarding the execution of these permutations in cache hierarchies, with particular emphasis on the cache-oblivious setting. we first bound from below the work needed to execute a rational permutation with an optimal cache complexity. then, we develop a cache-oblivious algorithm to perform any rational permutation, which exhibits optimal work and cache complexities under the tall cache assumption. we finally show that for certain families of rational permutations (including matrix transposition and bit reversal) no cache-oblivious algorithm can exhibit optimal cache complexity for all values of the cache parameters. this latter result specializes the one proved by brodal and fagerberg for general permutations to the case of rational permutations, and provides further evidence that the tall cache assumption is often necessary to attain cache optimality in the context of cache-oblivious algorithms.
parametric synchronizations in mobile nominal calculi. we present and compare p-prisma and f-prisma, two parametric calculi that can be instantiated with different interaction policies, defined as synchronization algebras with mobility of names (sams). in particular, p-prisma is based on name transmission (p-sam), like @p-calculus, and thus exploits directional (input-output) communication only, while f-prisma is based on name fusion (f-sam), like fusion calculus, and thus exploits a more symmetric form of communication. however, p-prisma and f-prisma can easily accommodate many other high-level synchronization mechanisms than the basic ones available in @p-calculus and fusion, hence allowing for the development of a general meta-theory of mobile calculi. we define for both the labeled operational semantics and a form of strong bisimilarity, showing that the latter is compositional for any sam. we also discuss reduction semantics and weak bisimilarity. we give several examples based on heterogeneous sams, we investigate the case studies of @p-calculus and fusion calculus giving correspondence theorems, and we show how p-prisma can be encoded in f-prisma. finally, we show that basic categorical tools can help to relate and to compose sams and prisma processes in an elegant way.
theoretical advances in artificial immune systems. artificial immune systems (ais) constitute a relatively new area of bio-inspired computing. biological models of the natural immune system, in particular the theories of clonal selection, immune networks and negative selection, have provided the inspiration for ais algorithms. moreover, such algorithms have been successfully employed in a wide variety of different application areas. however, despite these practical successes, until recently there has been a dearth of theory to justify their use. in this paper, the existing theoretical work on ais is reviewed. after the presentation of a simple example of each of the three main types of ais algorithm (that is, clonal selection, immune network and negative selection algorithms respectively), details of the theoretical analysis for each of these types are given. some of the future challenges in this area are also highlighted.
weighted monadic datalog. based on monadic datalog, we introduce the concept of weighted monadic datalog over unranked trees. this provides a query language that can be used to extract quantitative information from semi-structured databases where the quantities are taken from some semiring s. we show that weighted monadic datalog is as expressive as weighted tree automata on unranked trees. moreover, we prove that a query can be evaluated efficiently on an unranked tree provided that (i) s is commutative and the underlying datalog program is non-circular or (ii) s is a finite and commutative @w-cpo semiring.
a polynomial nominal unification algorithm. nominal syntax includes an abstraction operator and a primitive notion of name swapping, that can be used to represent in a simple and natural way systems that include binders. nominal unification (i.e., solving @a-equality constraints between nominal terms) has applications in rewriting and logic programming, amongst others. it is decidable: urban, pitts and gabbay gave a nominal unification algorithm that finds the most general solution to a nominal matching or unification problem, if one exists. a naive implementation of this algorithm is exponential in time; here we describe an algorithm based on a graph representation of nominal terms with lazy propagation of swappings, and show that it is polynomial.
testing data processing-oriented systems from stream x-machine models. one of the great benefits of using a stream x-machine to specify a system is its associated testing method. under certain design for test conditions, this method produces a test suite that can determine the correctness of the implementation under test (iut), provided that the processing functions of the stream x-machine specification have been correctly implemented. the method was originally developed for controllable stream x-machines. a recent paper generalizes the original method by considering specifications that do not meet the controllability requirement. however, it is still required that a controllable stream x-machine model of the iut exists and the size of the test suite produced strongly depends on the (estimated) upper bound on the number of states of this controllable model. while this assumption is in general reasonable for most interactive systems, it may produce unmanageable test suites for even simple data processing-oriented applications. this paper provides a new variant of the stream x-machine based testing method that no longer depends on the size of a controllable model of the iut. in data processing-oriented applications, the new method can drastically reduce the size of the test suite produced at the expense of a (possibly) more complex generation process.
population size versus runtime of a simple evolutionary algorithm. evolutionary algorithms (eas) find numerous applications, and practical knowledge on eas is immense. in practice, sophisticated population-based eas employing selection, mutation and crossover are applied. in contrast, theoretical analysis of eas often concentrates on very simple algorithms such as the (1+1) ea, where the population size equals 1. in this paper, the question is addressed whether the use of a population by itself can be advantageous. a population-based ea that neither makes use of crossover nor any diversity-maintaining operator is investigated on an example function. it is shown that an increase of the population size by a constant factor decreases the expected runtime from exponential to polynomial. thereby, the best gap known so far is improved from superpolynomial vs. polynomial to exponential vs. polynomial. moreover, it is proved that the exponential and polynomial runtime bounds occur with a probability exponentially close to one if the population size is a constant (resp., a small polynomial). finally, a second example function, where only a small population leads to a polynomial runtime, and a hierarchy result on the appropriate population size are presented. the analyses show formally how the population size can lead to different attractors in the search space.
comparing evolutionary algorithms to the (1+1)-ea. in this paper, we study the conditions in which the random hill-climbing algorithm (1 + 1)-ea compares favorably to other evolutionary algorithms (eas) in terms of fitness function distribution at a given iteration and with respect to the average optimization time. our approach is applicable when the reproduction operator of an evolutionary algorithm is dominated by the mutation operator of the (1 + 1)-ea. in this case one can extend the lower bounds obtained for the expected optimization time of the (1 + 1)-ea to other eas based on the dominated reproduction operator. this method is demonstrated on the sorting problem with ham landscape and the exchange mutation operator. we consider several simple examples where the (1 + 1)-ea is the best possible search strategy in the class of the eas.
arity hierarchy for temporal logics. a major result concerning temporal logics is kamp's theorem which states that the pair of modalities ''until'' and ''since'' is expressively complete for the first-order fragment of the monadic logic over the linear-time canonical model of naturals. the paper concerns the expressive power of temporal logics over trees. the main result states that in contrast to kamp's theorem, for every n there is a modality of arity n definable by a monadic logic formula, which is not equivalent over trees to any temporal logic formula which uses modalities of arity less than n. its proof takes advantage of an instance of shelah's composition theorem.this result has interesting corollaries, for instance reproving that ctl^* and ectl^+ have no finite basis.
density elimination. density elimination, a close relative of cut elimination, consists of removing applications of the takeuti-titani density rule from derivations in gentzen-style (hypersequent) calculi. its most important use is as a crucial step in establishing standard completeness for syntactic presentations of fuzzy logics; that is, completeness with respect to algebras based on the real unit interval [0,1]. this paper introduces the method of density elimination by substitutions. for general classes of (first-order) hypersequent calculi, it is shown that density elimination by substitutions is guaranteed by known sufficient conditions for cut elimination. these results provide the basis for uniform characterizations of calculi complete with respect to densely and linearly ordered algebras. standard completeness follows for many first-order fuzzy logics using a dedekind-macneille-style completion and embedding.
abstract interpretation and types for systems biology. abstract interpretation is a theory of abstraction that has been introduced for the analysis of programs. in particular, it has proved useful for organizing the multiple semantics of a given programming language in a hierarchy corresponding to different detail levels, and for defining type systems for programming languages and program analyzers in software engineering. in this paper, we investigate the application of these concepts to systems biology formalisms. more specifically, we consider the systems biology markup language sbml, and the biochemical abstract machine biocham with its differential, stochastic, discrete and boolean semantics. we first show how all of these different semantics, except the differential one, can be formally related by simple galois connections. then we define three type systems: one for checking or inferring the functions of proteins in a reaction model, one for checking or inferring the activation and inhibition effects of proteins in a reaction model, and another one for checking or inferring the topology of compartments or locations. we show that the framework of abstract interpretation elegantly applies to the formalization of these further abstractions, and to the implementation of linear or quadratic time type checking as well as type inference algorithms. furthermore, we show a theorem of independence of the graph of activation and inhibition effects from the kinetic expressions in the reaction model, under general conditions. through some examples, we show that the analysis of biochemical models by type inference provides accurate and useful information. interestingly, such a mathematical formalization of the abstractions commonly used in systems biology already provides some guidelines for the extensions of biochemical reaction rule languages.
universality and programmability of quantum computers. manin, feynman, and deutsch have viewed quantum computing as a kind of universal physical simulation procedure. much of the writing about quantum logic circuits and quantum turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. the problem of universality has been addressed most famously in a paper by deutsch, and later by bernstein and vazirani as well as kitaev and solovay. the quantum logic circuit model, developed by feynman and deutsch, has been more prominent in the research literature than deutsch's quantum turing machines. quantum turing machines form a class closely related to deterministic and probabilistic turing machines and one might hope to find a universal machine in this class. a universal machine is the basis of a notion of programmability. the extent to which universality has in fact been established by the pioneers in the field is examined and this key notion in theoretical computer science is scrutinised in quantum computing by distinguishing various connotations and concomitant results and problems.
when-and how-can a cellular automaton be rewritten as a lattice gas? both cellular automata (ca) and lattice-gas automata (lg) provide finite algorithmic presentations for certain classes of infinite dynamical systems studied by symbolic dynamics; it is customary to use the terms 'cellular automaton' and 'lattice gas' for a dynamic system itself as well as for its presentation. the two kinds of presentation share many traits but also display profound differences on issues ranging from decidability to modeling convenience and physical implementability. following a conjecture by toffoli and margolus, it had been proved by kari that any invertible ca, at least up to two dimensions, can be rewritten as an isomorphic lg. but until now it was not known whether this is possible in general for noninvertible ca-which comprise ''almost all'' ca and represent the bulk of examples in theory and applications. even circumstantial evidence-whether in favor or against-was lacking. here, for noninvertible ca, (a) we prove that an lg presentation is out of the question for the vanishingly small class of surjective ones. we then turn our attention to all the rest-noninvertible and nonsurjective-which comprise all the typical ones, including conway's 'game of life'. for these (b) we prove by explicit construction that all the one-dimensional ones are representable as lg, and (c) we present and motivate the conjecture that this result extends to any number of dimensions. the tradeoff between dissipation rate and structural complexity implied by the above results have compelling implications for the thermodynamics of computation at a microscopic scale.
interference automata. we propose a computing model, the two-way optical interference automata (2oia), that makes use of the phenomenon of optical interference. we introduce this model to investigate the increase in power, in terms of language recognition, of a classical deterministic finite automaton (dfa) when endowed with the facility of interference. the question is in the spirit of two-way finite automata with quantum and classical states (2qcfa) [a. ambainis, j. watrous, two-way finite automata with quantum and classical states, theoret. comput. sci. 287 (1) (2002) 299-311] wherein the classical dfa is augmented with a quantum component of constant size. we test the power of 2oia against the languages mentioned in the above paper. we give efficient 2oia algorithms to recognize languages for which 2qcfa machines have been shown to exist, as well as languages whose status vis-a-vis 2qcfa has been posed as open questions. having a dfa as a component, it trivially recognizes regular languages. we show that our model can recognize all languages recognized by 1-way deterministic blind counter automata. finally we show the existence of a language that cannot be recognized by a 2oia but which can be recognized by an o(n^3) space turing machine.
uniformity and the taylor expansion of ordinary lambda-terms. we define the complete taylor expansion of an ordinary lambda-term as an infinite linear combination-with rational coefficients-of terms of a resource calculus similar to boudol's lambda-calculus with multiplicities (or with resources). in our resource calculus, all applications are (multi)linear in the algebraic sense, i.e. commute with linear combinations of the function or the argument. we study the collective behaviour of the beta-reducts of the terms occurring in the taylor expansion of any ordinary lambda-term, using, in a surprisingly crucial way, a uniformity property that they enjoy. as a corollary, we obtain (the main part of) a proof that this taylor expansion commutes with bohm tree computation, syntactically.
polyhedra genus theorem and euler formula: a hypermap-formalized intuitionistic proof. this article presents formalized intuitionistic proofs for the polyhedra genus theorem, the euler formula and a sufficient condition of planarity. they are based on a hypermap model for polyhedra and on formal specifications in the calculus of inductive constructions. first, a type of free maps is inductively defined from three atomic constructors. next, a hierarchy of types defined by invariants, with operations constrained by preconditions, is built on the free maps: hypermaps, orientated combinatorial maps and a central notion of quasi-hypermaps. besides, the proofs of their properties are established until the genus theorem and the euler formula, mainly using a simple induction principle based on the free map term algebra. finally, a constructive sufficient condition for polyhedra to be planar is set and proved. the whole process is assisted by the interactive coq proof system.
a dna computing inspired computational model. in this paper we propose a universal rewriting system whose computational steps closely resemble the manner in which nature computes double stranded dna molecules. the basic data structure is given by a couple of strings paired by a complementarity relation (such as the watson-crick one), and the rewriting rules have a biotechnological implementation as dna computing standard procedures. the antiparallel orientation of the formal strings laying on the double structure is taken into consideration, as in [g. franco, v. manca, an algorithmic analysis of dna structure, soft computing-a fusion of foundations, methodologies and applications 9 (10) (2005) 761-768] it was shown to be essential for some informational and computational aspects underlying the dna autoduplication process. the universality of such a system has been proved and the biotechnological details of a possible implementation have been outlined. moreover, the membrane system which turned out to be the natural context to describe our system in [g. franco, m. margenstern, computing by floating strings, in: n. busi, c. zandron (eds.), proceedings of the first workshop on membrane computing and biologically inspired process calculi (mecbic 2006), july 9, s. servolo, venice, italy, in: entcs, vol. 171(issue 2), july 2007, pp. 95-104] has been proposed here in more technical detail, and the announced extension work has been developed.
(mem)brane automata. we introduce the notion of a p automaton with marked membranes, a p"p"p automaton for short, which is an accepting variant of p systems. the concept is motivated by the theory of p systems, brane calculi, and the traditional concept of automata. in p systems with marked membranes, bio-molecules (proteins) are allowed to move through the membranes and to attach onto or to de-attach from the membranes. the membrane system evolves according to rules which are defined over multisets of proteins and describe the above actions. in addition to these features, the p automaton with marked membranes is able to consume inputs from its environment, i.e. multisets of proteins, which might influence the behaviour of the system. the result of the computation is the set of multiset sequences consumed by the skin membrane, supposing that the p"p"p automaton started functioning in the initial configuration and entered a final configuration at halting. we show that any recursively enumerable language can be obtained as the language accepted by a p"p"p automaton modulo a simple computable mapping.
relating continuous and discrete pepa models of signalling pathways. pepa and its semantics have recently been extended to model biological systems. in order to cope with massive quantities of processes (as is usually the case when considering biological reactions) the model is interpreted in terms of a small set of coupled ordinary differential equations (odes) instead of a large state space continuous time markov chain (ctmc). so far the relationship between these two semantics of pepa had not been established. this is the goal of the present paper. after introducing a new extension of pepa, denoted pepa+@p, that allows models to capture both mass action law and bounded capacity law cooperations, the relationship between these two semantics is demonstrated. the result relies on kurtz's theorem that expresses that a set of odes can be, in some sense, considered as the limit of pure jump markov processes.
a uniform family of tissue p systems with cell division solving 3-col in a linear time. several examples of the efficiency of cell-like p systems regarding the solution of np-complete problems in polynomial time can be found in the literature(obviously, trading space for time). recently, different new models of tissue-like p systems have received much attention from the scientific community. in this paper we present a linear-time solution to an np-complete problem from graph theory, the 3-coloring problem, and we discuss the suitability of tissue-like p systems as a framework to address the efficient solution to intractable problems.
generalized communicating p systems. this paper considers a generalization of various communication models based on the p system paradigm where two objects synchronously move across components. more precisely, the model uses blocks of four cells such that pairs of objects from two input cells travel together to target output cells. it is shown that the model introduced, based on interactions between blocks, is complete, being able to generate all recursively enumerable sets of natural numbers. it is also proven that completeness is achievable by using a minimal interaction between blocks, i.e. every pair of cells is the input or output for at most one block. it is also shown that the concepts introduced in this paper to define the model may be simulated by more particular communication primitives, including symport, antiport and uniport rules. this enables us to automatically translate a system using interaction rules in any of minimal symport, minimal antiport or conditional uniport p systems.
the metabolic algorithm for p systems: principles and applications. metabolic p systems, shortly mp systems, are a special class of p systems, introduced for expressing biological metabolism. an mp system evolution is given by a metabolic algorithm, a deterministic strategy, where the classical viewpoint on metabolic dynamics, in terms of ordinary differential equations, is replaced by suitable generalizations of chemical principles. the basic principles of mp systems are given and their main aspects are explained by means of examples of biological modeling. a new kind of regulation mechanism is outlined, which could be the basis for a more efficient construction of computational models from experimental data of specific metabolic processes.