waashk/dblp huggingface dataset:
watson-crick d0l systems with regular triggers. watson-crick complementarity has been used as a basis for massive paral- lelism in dna computing. also its use in an operational sense has turned out to be very promising in the study of watson-crick d0l systems. the latter generalize d0l systems in a way not investigated so far in the the- ory of lindenmayer systems. the complexity of the "trigger" is crucial for decidability properties concerning watson-crick d0l systems. the purpose of this paper is to settle the basic decision problems in the case of regular triggers.
semantic models of a timed distributed dataspace architecture. we investigate various formal aspects of a distributed dataspace architecture in which data storage is based on time stamps. an operational and a denotational semantics have been defined and the equivalence of these two formulations has been proved. moreover, the denotational semantics is fully abstract with respect to the observation of produced data items. it is used as a basis for compositional reasoning about components, supported by the interactive theorem prover pvs. we use this framework for a small example where components make mutual assumptions about each other's output.
simple permutations mix well. we study the random composition of a small family of o(n3) simple permutations on {0, 1}n. specifically, we ask what is the number of compositions needed to achieve a permutation that is close to k-wise independent. we improve on a result of gowers [an almost m-wise independent random permutation of the cube, combin. probab. comput. 5(2) (1996) 119-130] and show that up to a polylogarithmic factor, n3k3 compositions of random permutations from this family suffice. we further show that the result applies to the stronger notion of k-wise independence against adaptive adversaries. this question is essentially about the rapid mixing of the random walk on a certain graph, and we approach it using a new technique to construct canonical paths. we also show that if we are willing to use a much larger family of simple permutations then we can guarantee closeness to k-wise independence with fewer compositions and fewer random bits.
computing unsatisfiable k-sat instances with few occurrences per variable. (k, s)-sat is the propositional satisfiability problem restricted to instances where each clause has exactly k distinct literals and every variable occurs at most s times. it is known that there exists an exponential function f such that for s ≤ f(k) all (k, s)-sat instances are satisfiable, but (k, f (k) + 1)- sat is already np-complete (k ≥ 3). exact values of f are only known for k = 3 and 4, and it is open whether f is computable. we introduce a computable function f1 which bounds f from above and determine the values of f1 by means of a calculus of integer sequences. this new approach enables us to improve the best known upper bounds for f(k), generalizing the known constructions for unsatisfiable (k, s)-sat instances for small k.
on the reachability problem for 5-dimensional vector addition systems. the reachability set for vector addition systems of dimension less than or equal to five are shown to be effectively computable semilinear sets. thus reachability, equvalence and containment are decidable up to dimension 5. an example of a non-semilinear reachability set is given for dimension 6. keywords and phrases: vector addition system, petri net, semilinear set, algorithms, decidability.
storage-to-tree transducers with look-ahead. we generalize engelfriet's decomposition result stating that the class of transformations induced by top-down tree transducers with regular look-ahead is equal to the composition of the class of top-down tree transformations and the class of linear tree homomorphisms. replacing the input trees with an arbitrary storage type, the top-down tree transducers are turned into regular storage-to-tree transducers. we show that the class of transformations induced by regular storage-to-tree transducers with positive look-ahead is equal to the composition of the class of transformations induced by regular storage-to-tree transducers with the class of linear tree homomorphisms. we also show that the classes of transformations induced by both io and oi context-free storage-to-tree transducers are closed under positive look-ahead, and are closed under composition with linear tree homomorphisms.
rank two bipartite bound entangled states do not exist. we explore the relation between the rank of a bipartite density matrix and the existence of bound entanglement. we show a relation between the rank, marginal ranks, and distillability of a mixed state and use this to prove that any rank n bound entangled state must have support on no more than an n × n hilbert space. a direct consequence of this result is that there are no bipartite bound entangled states of rank two. we also show that a separability condition in terms of a quantum entropy inequality is associated with the above results. we explore the idea of how many pure states are needed in a mixture to cancel the distillable entanglement of a schmidt rank n pure state and provide a lower bound of n - 1. we also prove that a mixture of a non-zero amount of any pure entangled state with a pure product state is distillable.
boolean operations and inclusion test for attribute-element constraints. the history of schema languages for xml is (roughly) an increase of expressiveness. while early schema languages mainly focused on the element structure, clark first paid an equal attention to attributes by allowing both element and attribute constraints in a single constraint expression (we call his mechanism "attribute-element constraints"). in this paper, we investigate intersection and difference operations and inclusion test for attribute-element constraints, in view of their importance in static typechecking for xml processing programs. the contributions here are (1) proofs of closure under intersection and difference as well as decidability of inclusion test and (2) algorithm formulations incorporating a "divide-and-conquer" strategy for avoiding an exponential blowup for typical inputs.
periodicity and arithmetic-periodicity in hexadecimal games. we investigate 1-, 2- and some k-digit (k ≥ 3) hexadecimal games with the help of a new arithmetic-periodicity theorem. we also note that not all hexadecimal games are periodic or arithmetic-periodic.
on the power of randomized multicounter machines. one-way two-counter machines represent a universal model of computation. here we consider the polynomial-time classes of multicounter machines with a constant number of reversals and separate the computational power of nondeterminism, randomization and determinism. for instance, we show that polynomial-time one-way multicounter machines, with error probability tending to zero with growing input length, can recognize languages that cannot be accepted by polynomial-time nondeterministic two-way multicounter machines with a bounded number of reversals. a similar result holds for the comparison of determinism and one-sided-error randomization, and of determinism and las vegas randomization.
dependences related to strict binary relations. in this paper we study dependences on a free monoid x* and their relations to strict binary relations on x*. as a consequence we characterize strict binary relations by the notion of dependence. moreover, some results concerning the relationship between dependences and codes are also obtained. a visualization of this work is provided by the theory of graph.
embedding longest fault-free paths onto star graphs with more vertex faults. the n-dimensional star graph sn belongs to a class of bipartite graphs, and it is recognized as an attractive alternative to the hypercube. since s1, s2, and s3 have trivial structures, we focus our attention on sn with n ≥ 4 in this paper. let f(sn) be the set of vertex faults. previously, it was shown that when |f(sn)| ≤ n -5, sn with n ≥ 6 can embed a longest fault-free path of length at least n! -2|f(sn)| -1 (respectively, n! -2|f(sn)| -2) between two arbitrary vertices in different partite sets (respectively, the same partite set) [longest fault-free paths in star graphs with vertex faults, theoretical computer science 262 (2001) 215-227]. in this paper, we improve the above result by tolerating more faults (|f(sn)|≤ n -3) to embed a longest fault-free path between two arbitrary vertices in sn, n ≥ 4.
pc trees and circular-ones arrangements. a 0-1 matrix has the consecutive-ones property if its columns can be ordered so that the ones in every row are consecutive. it has the circular-ones property if its columns can be ordered so that, in every row, either the ones or the zeros are consecutive. pq trees are used for representing all consecutive-ones orderings of the columns of a matrix that have the consecutive-ones property. we give an analogous structure, called a pc tree, for representing all circular-ones orderings of the columns of a matrix that has the circular-ones property. no such representation has been given previously. in contrast to pq trees, pc trees are unrooted. we obtain a much simpler algorithm for computing pq trees that those that were previously available, by adding a zero column, x, to a matrix, computing the pc tree, and then picking the pc tree up by x to root it.
property-preserving subnet reductions for designing manufacturing systems with shared resources. this paper handles two problems in manufacturing system design: resource sharing and system abstraction. in a manufacturing system, resources such as robots, machines, etc. are shared by several processes. when the resources are switched from one process to another, they may need some modifications such as cleaning oil, adding equipments and so on. previous designing methods assume that the resources have no intermediate modifications. hence, they need to be extended to handle such kinds of resource-sharing problems. as for abstraction, modeling operations with single places in manufacturing system design is very popular. from the viewpoint of verification, the objective is to verify whether the reduced model has the same desirable properties as the original one. this paper presents three kinds of property-preserving subnet reduction methods. for each reduction method, conditions are presented for ensuring that the properties liveness, boundedness and reversibility are preserved. applications of these reduction methods to handling the above resource sharing and system abstraction problems are illustrated with an example from the manufacturing system.
approximation of walrasian equilibrium in single-minded auctions. we consider a social optimization model of pricing scheme in single-minded auctions, in cases where walrasian equilibrium does not exist. we are interested in the maximization of the ratio, r, of happy bidders over all agents, in a feasible allocation-pricing scheme. we show np-hardness of the optimization problem, establish lower and upper bounds of r, as well as develop greedy algorithms to approximate the optimal value of r.
simulations in coalgebra. a new approach to simulations is proposed within the theory of coalgebras by taking a notion of order on a functor as primitive. such an order forms a basic building block for a "lax relation lifting", or "relator" as used by other authors. simulations appear as coalgebras of this lifted functor, and similarity as greatest simulation. two-way similarity is then similarity in both directions. in general, it is different from bisimilarity (in the usual coalgebraic sense), but a sufficient condition is formulated (and illustrated) to ensure that bisimilarity and two-way similarity coincide. also, suitable conditions are identified which ensures that similarity on a final coalgebra forms an (algebraic) dcpo structure. this involves a close investigation of the iterated applications fn(0) and fn(1) of a functor f with an order to the initial algebras and final objects.
admissible digit sets. we examine a special case of admissible representations of the closed interval, namely those which arise via sequences of a finite number of möbius transformations. we regard certain sets of möbius transformations as a generalized notion of digits and introduce sufficient conditions that such a "digit set" yields an admissible representation of [0,+ ∞]. furthermore, we establish the productivity and correctness of the homographic algorithm for such "admissible" digit sets. we present the stern-brocot representation and a modification of same as a working example throughout.
counting lattice paths taking steps in infinitely many directions under special access restrictions. we count lattice paths that are confined to the first quadrant by the nature of their step vectors. if no further restrictions apply, a path can go from any point to infinitely many others, but each point on the path has only finitely many predecessors. by "further restrictions" we mean a boundary line above which the paths may have to stay. access privilege to the boundary line itself is granted from certain lattice points in the form of a special access step set, which itself may be infinite. we also count the number of paths that contact the weak boundary a given number of times. we approach explicit solutions of such enumeration problems via sheffer polynomials and functionals, using results of the umbral calculus.
linear-time algorithms for the hamiltonian problems on distance-hereditary graphs. a hamiltonian path of a graph g is a simple path that contains each vertex of g exactly once. a hamiltonian cycle of a graph is a simple cycle with the same property. the hamiltonian path (resp. cycle) problem involves testing whether a hamiltonian path (resp. cycle) exists in a graph. the 1hp (resp. 2hp) problem is to determine whether a graph has a hamiltonian path starting from a specified vertex (resp. starting from a specified vertex and ending at the other specified vertex). the hamiltonian problems include the hamiltonian path, hamiltonian cycle, 1hp, and 2hp problems. a graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. in this paper, we present a unified approach to solving the hamiltonian problems on distance-hereditary graphs in linear time.
chebyshev polynomials over finite fields and reversibility of -automata on square grids. using number theory on function fields and algebraic number fields, we prove results about chebyshev polynomials over finite prime fields to investigate reversibility of two-dimensional additive cellular automata on finite square grids. for example, we show that there are infinitely many primitive irreversible additive cellular automata on square grids when the base field has order two or three.
probabilistic guarded commands mechanized in . the probabilistic guarded-command language (pgcl) contains both demonic and probabilistic non-determinism, which makes it suitable for reasoning about distributed random algorithms. proofs are based on weakest precondition semantics, using an underlying logic of real- (rather than boolean-)valued functions.we present a mechanization of the quantitative logic for pgcl using the hol theorem prover, including a proof that all pgcl commands, satisfy the new condition sublinearity, the quantitative generalization of conjunctivity for standard gcl.the mechanized theory also supports the creation of an automatic proof tool which takes as input an annotated pgcl program and its partial correctness specification, and derives from that a sufficient set of verification conditions. this is employed to verify the partial correctness of the probabilistic voting stage in rabin's mutual-exclusion algorithm.
utilization of nonclairvoyant online schedules. this paper addresses the analysis of nondelay, nonpreemptive, nonclairvoyant online schedules for independent jobs on m identical machines. in our online model, all jobs are submitted over time. we show that the commonly used makespan criterion is not well suited to describe utilization for this online problem. therefore, we directly address utilization and determine the maximum deviation from the optimal utilization for the given scheduling problem.
coding properties of dna languages. the computation language of a dna-based system consists of all the words (dna strands) that can appear in any computation step of the system. in this work we define properties of languages which ensure that the words of such languages will not form undesirable bonds when used in dna computations. we give several characterizations of the desired properties and provide methods for obtaining languages with such properties. the decidability of these properties is addressed as well. as an application we consider splicing systems whose computation language is free of certain undesirable bonds and is generated by nearly optimal comma-free codes.
on finite-state approximants for probabilistic computation tree logic. we generalize the familiar semantics for probabilistic computation tree logic from finite-state to infinite-state labelled markov chains such that formulas are interpreted as measurable sets. then we show how to synthesize finite-state abstractions which are sound for full probabilistic computation tree logic and in which measures are approximated by monotone set functions. this synthesis of sound finite-state approximants also applies to finite-state systems and is a probabilistic analogue of predicate abstraction. sufficient and always realizable conditions are identified for obtaining optimal such abstractions for probabilistic propositional modal logic.
approximate string matching using compressed suffix arrays. let t be a text of length n and p be a pattern of length m, both strings over a fixed finite alphabet a. the k-difference (k-mismatch, respectively) problem is to find all occurrences of p in t that have edit distance (hamming distance, respectively) at most k from p. in this paper we investigate a well-studied case in which t is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster. we give a solution using an o(n log n) bits indexing data structure with o(|a|kmkċmax(k, log n) +occ) query time, where occ is the number of occurrences. the best previous result requires o(n log n) bits indexing data structure and gives o(|a|kmk+2 + occ) query time. our solution also allows us to exploit compressed suffix arrays to reduce the indexing space to o(n) bits, while increasing the query time by an o(log n) factor only.
uniform asymptotics of some abel sums arising in coding theory. we derive uniform asymptotic expressions of some abel sums appearing in some problems in coding theory and indicate the usefulness of these sums in other fields, like empirical processes, machine maintenance, analysis of algorithms, probabilistic number theory, queuing models, etc.
a complementary survey on double-loop networks. we give a survey on double-loop networks with emphasis on new development since the surveys in 1986, 1991 and 1995.
a survey on multi-loop networks. bermond, comellas and hsu gave an excellent survey on multi-loop networks, directed and undirected, in 1995, but only one and half page is on loop networks other than the directed double-loop. hwang recently gave a substantial survey, but only on the directed double-loop. this survey is a companion of the latter survey by focusing on the other loop networks.
an asymptotic theory for recurrence relations based on minimization and maximization. we derive asymptotic approximations for the sequence f(n) defined recursively by f(n) = min1≤j<n {f(j) + f(n - j)} + g(n), when the asymptotic behavior of g(n) is known. our tools are general enough and applicable to another sequence f(n) = max1 ≤j<n{f(j) + f(n - j) + min{g(j),g(n-j)}}, also frequently encountered in divide-and-conquer problems. applications of our results to algorithms, group testing, dichotomous search, etc. are discussed.
some permutation routing algorithms for low-dimensional hypercubes. oblivious permutation routing in binary d-cubes has been well studied in the literature. in a permutation routing, each node initially contains a packet with a destination such that all the 2d destinations are distinct. kaklamanis et al. (math. syst. theory 24 (1991) 223-232) used the decomposability of hypercubes into hamiltonian circuits to give an asymptotically optimal routing algorithm. the notion of "destination graph" was first introduced by borodin and hopcroft to derive lower bounds on routing algorithms. this idea was recently used by grammatikakis et al. (proceedings of the advancement in parallel computing, elsevier, amsterdam, 1993) to construct many-one routing algorithms for the binary 2-cube and 3-cube. in the present paper, further theoretical development is made along this line. it is then applied to obtain algorithms for binary d-cubes with d up to 12, which compare favorably with the above-mentioned "hamiltonian circuit" algorithm. some results on t-nary cubes with t&ge;3 are also obtained.
discrete lawvere theories and computational effects. countable lawvere theories model computational effects such as exceptions, side-effects, interactive input/output, nondeterminism and probabilistic nondeterminism. the category of countable lawvere theories has sums, tensors, and distributive tensors, modelling natural combinations of such effects. it is also closed under taking images. enrichment in a category such as ωcpo allows one to extend this modelling of computational effects to account for partiality and recursion. sum and tensor extend to enriched countable lawvere theories, but distributive tensor and image do not. so here we introduce discrete countable enriched lawvere theories in order to allow natural definitions and accounts of distributive tensor and image. a discrete countable enriched lawvere theory is, in a sense we make precise, an enriched lawvere theory with discrete arities. we show that they include all our leading examples of computational effects and are closed under sum and tensor. and we develop notions of enriched operad and enriched multicategory to support the definition.
combining effects: sum and tensor. we seek a unified account of modularity for computational effects. we begin by reformulating moggi's monadic paradigm for modelling computational effects using the notion of enriched lawvere theory, together with its relationship with strong monads; this emphasises the importance of the operations that produce the effects. effects qua theories are then combined by appropriate bifunctors on the category of theories. we give a theory for the sum of computational effects, which in particular yields moggi's exceptions monad transformer and an interactive input/output monad transformer. we further give a theory of the commutative combination of effects, their tensor, which yields moggi's side-effects monad transformer. finally, we give a theory of operation transformers, for redefining operations when adding new effects; we derive explicit forms for the operation transformers associated to the above monad transformers.
glueing and orthogonality for models of linear logic. we present the general theory of the method of glueing and associated technique of orthogonality for constructing categorical models of all the structure of linear logic: in particular we treat the exponentials in detail. we indicate simple applications of the methods and show that they cover familiar examples.