waashk/dblp huggingface dataset:
p systems with minimal parallelism. a current research topic in membrane computing is to find more realistic p systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. we contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). weak as it might look, this minimal parallelism still leads to universality. we first prove this for the case of symport/antiport rules. the result is obtained both for generating and accepting p systems, in the latter case also for systems working deterministically. then, we consider p systems with active membranes, and again the usual results are obtained: universality and the possibility to solve np-complete problems in polynomial time (by trading space for time).
algorithmic analysis of polygonal hybrid systems, part i: reachability. in this work we are concerned with the formal verification of two-dimensional non-deterministic hybrid systems, namely polygonal differential inclusion systems (spdis). spdis are a class of non-deterministic systems that correspond to piecewise constant differential inclusions on the plane, for which we study the reachability problem. our contribution is the development of an algorithm for solving exactly the reachability problem of spdis. we extend the geometric approach due to maler and pnueli [o. maler, a. pnueli. reachability analysis of planar multi-linear systems. in: c. courcoubetis (ed.), cav'93, in: lncs, vol. 697, springer-verlag, 1993, pp. 194-209] to non-deterministic systems, based on the combination of three techniques: the representation of the two-dimensional continuous-time dynamics as a one-dimensional discrete-time system (using poincare maps), the characterization of the set of qualitative behaviors of the latter as a finite set of types of signatures, and acceleration used to explore reachability according to each of these types.
hardness of approximating the minimum solutions of linear diophantine equations. let 1@?pnp, it is hard to approximate the minimum solutions of linear diophantine equations in @?"p norm within any constant factor and it is also hard to approximate the minimum solutions of linear diophantine equations in @?"p norm within the factor n^c^/^l^o^g^l^o^g^n for some constant c>0 where n is the number of variables in the equations.
from truth to computability ii. computability logic is a formal theory of computational tasks and resources. formulas in it represent interactive computational problems, and ''truth'' is understood as algorithmic solvability. interactive computational problems, in turn, are defined as games between a machine and its environment, with logical operators standing for operations on games. within the program of finding axiomatizations for incrementally rich fragments of this semantically introduced logic, the earlier article ''from truth to computability i'' proved soundness and completeness for system cl3, whose language has the so-called parallel connectives (including negation), choice connectives, choice quantifiers, and blind quantifiers. the present paper extends that result to the significantly more expressive system cl4 with the same collection of logical operators. what makes cl4 expressive is the presence of two sorts of atoms in its language: elementary atoms, representing elementary computational problems (i.e. predicates, i.e. problems of zero degree of interactivity), and general atoms, representing arbitrary computational problems. cl4 conservatively extends cl3, with the latter being nothing but the general-atom-free fragment of the former. removing the blind (classical) group of quantifiers from the language of cl4 is shown to yield a decidable logic despite the fact that the latter is still first-order.
splitting atoms safely. the aim of this paper is to make a contribution to (compositional) development methods for concurrent programs. in particular, it takes a fresh look at a number of familiar ideas including the problem of interference. some subtle issues of observability-including granularity-are explored. based on these points, the paper sets out some requirements for an approach to developing systems by ''splitting atoms safely''.
average case analysis for tree labelling schemes. we study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least 18log^2n-o(logn) bits, where n is the number of vertices in the input tree t. they also gave a separator-based labelling scheme that has the optimal label length @q(logn@?log(h"n(t))), where h"n(t) is the height of t. we present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. the two schemes always perform at least as well as the separator scheme. furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. with these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.
on codes defined by bio-operations. we consider the classes of @?-codes and @?-codes, which are superclasses of outfix and hyper-codes, respectively. these restrictions are based on the synchronized insertion operation, which serves as a model for the gene rearrangement function in certain unicellular organisms. we investigate the classes of @?-codes and @?-codes from a theoretical perspective, examine their relationships with traditional code classes and consider related decidability problems.
efficient algorithms for center problems in cactus networks. efficient algorithms for solving the center problems in weighted cactus networks are presented. in particular, we have proposed the following algorithms for the weighted cactus networks of size n: an o(nlogn) time algorithm to solve the 1-center problem, and an o(nlog^3n) time algorithm to solve the weighted continuous 2-center problem. we have also provided improved solutions to the general p-center problems in cactus networks. the developed ideas are then applied to solve the obnoxious 1-center problem in weighted cactus networks.
a uniform solution to sat using membrane creation. in living cells, new membranes are produced basically through two processes: mitosis and autopoiesis. these two processes have inspired two variants of cell-like membrane systems, namely p systems with active membranes and p systems with membrane creation. in this paper, we provide the first uniform, efficient solution to the sat problem in the framework of recogniser p systems with membrane creation using dissolution rules. recently the authors have proved that if the dissolution rules are not allowed to be used, then the polynomial complexity class associated with this variant of p systems is the standard complexity class p. this result, together with the main result of this paper, shows the surprising role of the apparently ''innocent'' operation of membrane dissolution. the use of this type of rule establishes the difference between efficiency and non-efficiency for p systems with membrane creation, and provides a barrier between p and np (assuming p
subjective-cost policy routing. we study a model of path-vector routing in which nodes' routing policies are based on subjective cost assessments of alternative routes. the routes are constrained by the requirement that all routes to a given destination must be confluent. we show that it is np-hard to determine whether there is a set of stable routes. we also show that it is np-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate the minimum cost closely. these hardness results hold even for very restricted classes of subjective costs. we then consider a model in which the subjective costs are based on the relative importance nodes place on a small number of objective cost measures. we show that a small number of confluent routing trees is sufficient for each node to have a route that nearly minimizes its subjective cost. we show that this scheme is trivially strategy proof and that it can be computed easily with a distributed algorithm. furthermore, we prove a lower bound on the number of trees required to contain a (1+@e)-approximately optimal route for each node and show that our scheme is nearly optimal in this respect.
fitness landscape of the cellular automata majority problem: view from the "olympus". in this paper we study cellular automata (cas) that perform the computational majority task. this task is a good example of what the phenomenon of emergence in complex systems is. we take an interest in the reasons that make this particular fitness landscape a difficult one. the first goal is to study the landscape as such, and thus it is ideally independent from the actual heuristics used to search the space. however, a second goal is to understand the features a good search technique for this particular problem space should possess. we statistically quantify in various ways the degree of difficulty of searching this landscape. due to neutrality, investigations based on sampling techniques on the whole landscape are difficult to conduct. so, we go exploring the landscape from the top. although it has been proved that no ca can perform the task perfectly, several efficient cas for this task have been found. exploiting similarities between these cas and symmetries in the landscape, we define the olympus landscape which is regarded as the ''heavenly home'' of the best local optima known (blok). then we measure several properties of this subspace. although it is easier to find relevant cas in this subspace than in the overall landscape, there are structural reasons that prevent a searcher from finding overfitted cas in the olympus. finally, we study dynamics and performance of genetic algorithms on the olympus in order to confirm our analysis and to find efficient cas for the majority problem with low computational cost.
randomized local search, evolutionary algorithms, and the minimum spanning tree problem. randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. the analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. after motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms.
counting distinct items over update streams. in data streaming applications, data arrives at rapid rates and in high volume, thus making it essential to process each stream update very efficiently in terms of both time and space. a data stream is a sequence of data records that must be processed continuously in an online fashion using sub-linear space and sub-linear processing time. we consider the problem of tracking the number of distinct items over data streams that allow insertion and deletion operations. we present two algorithms that improve on the space and time complexity of existing algorithms.
statistical zero knowledge and quantum one-way functions. one-way functions are a fundamental notion in cryptography, since they are the necessary condition for the existence of secure encryption schemes. most examples of such functions, including factoring, discrete logarithm or the rsa function, however, can be inverted with the help of a quantum computer. hence, it is very important to study the possibility of quantum one-way functions, i.e. functions which are easily computable by a classical algorithm but are hard to invert even by a quantum adversary. in this paper, we provide a set of problems that are good candidates for quantum one-way functions. these problems include graph non-isomorphism, approximate closest lattice vector and group non-membership. more generally, we show that any hard instance of circuit quantum sampling gives rise to a quantum one-way function. by the work of aharonov and ta-shma [d. aharonov, a. ta-shma, adiabatic quantum state generation and statistical zero knowledge, in: proceedings of stoc02 - symposium on the theory of computing, 2001], this implies that any language in statistical zero knowledge which is hard-on-average for quantum computers leads to a quantum one-way function. moreover, extending the result of impagliazzo and luby [r. impagliazzo, m. luby, one-way functions are essential for complexity based cryptography, in: proceedings of focs89 - symposium on foundations of computer science, 1989] to the quantum setting, we prove that quantum distributionally one-way functions are equivalent to quantum one-way functions.
longest increasing subsequences in windows based on canonical antichain partition. given a sequence @p"1@p"2...@p"n, a longest increasing subsequence (lis) in a window @p=@p"l@p"l"+"1...@p"r is a longest subsequence @s=@p"i"""1@p"i"""2...@p"i"""t such that l@?i"1|0@?i@?n-w}@?{@p,@p|i
a new algorithm based on copulas for var valuation with empirical calculations. this paper concerns the application of copula functions in var valuation. the copula function is used to model the dependence structure of multivariate assets. after the introduction of the traditional monte carlo simulation method and the pure copula method we present a new algorithm based on mixture copula functions and the dependence measure, spearman's rho. this new method is used to simulate daily returns of two stock market indices in china, shanghai stock composite index and shenzhen stock composite index, and then empirically calculate six risk measures including var and conditional var. the results are compared with those derived from the traditional monte carlo method and the pure copula method. from the comparison we show that the dependence structure between asset returns plays a more important role in valuating risk measures comparing with the form of marginal distributions.
decision-making based on approximate and smoothed pareto curves. we consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the pareto curve and (ii) the so-called decision maker's approach in which both criteria are combined into a single (usually nonlinear) objective function. previous work by papadimitriou and yannakakis showed how to efficiently approximate the pareto curve for problems like shortest path, spanning tree, and perfect matching. we wish to determine for which classes of combined objective functions the approximate pareto curve also yields an approximate solution to the decision maker's problem. we show that an fptas for the pareto curve also gives an fptas for the decision-maker's problem if the combined objective function is growth bounded like a quasi-polynomial function. if the objective function, however, shows exponential growth then the decision-maker's problem is np-hard to approximate within any polynomial factor. in order to bypass these limitations of approximate decision making, we turn our attention to pareto curves in the probabilistic framework of smoothed analysis. we show that in a smoothed model, we can efficiently generate the (complete and exact) pareto curve with a small failure probability if there exists an algorithm for generating the pareto curve whose worst-case running time is pseudopolynomial. this way, we can solve the decision-maker's problem w.r.t. any non-decreasing objective function for randomly perturbed instances of, e.g. shortest path, spanning tree, and perfect matching.
arithmetic computation in the tile assembly model: addition and multiplication. formalized study of self-assembly has led to the definition of the tile assembly model [erik winfree, algorithmic self-assembly of dna, ph.d. thesis, caltech, pasadena, ca, june 1998; paul rothemund, erik winfree, the program-size complexity of self-assembled squares, in: acm symposium on theory of computing, stoc02, montreal, quebec, canada, 2001, pp. 459-468]. research has identified two issues at the heart of self-assembling systems: the number of steps it takes for an assembly to complete, assuming maximum parallelism, and the minimal number of tiles necessary to assemble a shape. in this paper, i define the notion of a tile assembly system that computes a function, and tackle these issues for systems that compute the sum and product of two numbers. i demonstrate constructions of such systems with optimal @q(1) distinct tile types and prove the assembly time is linear in the size of the input.
complexity and approximation of the minimum recombinant haplotype configuration problem. we study the complexity and approximation of the problem of reconstructing haplotypes from genotypes on pedigrees under the mendelian law of inheritance and the minimum recombinant principle (mrhc). first, we show that the mrhc for simple pedigrees where each member has at most one mate and at most one child (i.e. binary-tree pedigrees) is np-hard. second, we present some approximation results for the mrhc problem, which are the first approximation results in the literature to the best of our knowledge. we prove that the mrhc on two-locus pedigrees or binary-tree pedigrees with missing data cannot be approximated unless p=np. next we show that the mrhc on two-locus pedigrees without missing data cannot be approximated within any constant ratio under the unique games conjecture and can be approximated within the ratio o(log(n)). our l-reduction for the approximation hardness gives a simple alternative proof that the mrhc on two-locus pedigrees is np-hard, which is much easier to understand than the original proof. we also show that the mrhc for tree pedigrees without missing data cannot be approximated within any constant ratio under the unique games conjecture, too. finally, we explore the hardness and approximation of the mrhc on pedigrees where each member has a bounded number of children and mates mirroring real pedigrees.
semantics of a sequential language for exact real-number computation. we study a programming language with a built-in ground type for real numbers. in order for the language to be sufficiently expressive but still sequential, we consider a construction proposed by boehm and cartwright. the non-deterministic nature of the construction suggests the use of powerdomains in order to obtain a denotational semantics for the language. we show that the construction cannot be modelled by the plotkin or smyth powerdomains, but that the hoare powerdomain gives a computationally adequate semantics. as is well known, hoare semantics can be used in order to establish partial correctness only. since computations on the reals are infinite, one cannot decompose total correctness into the conjunction of partial correctness and termination as is traditionally done. we instead introduce a suitable operational notion of strong convergence and show that total correctness can be proved by establishing partial correctness (using denotational methods) and strong convergence (using operational methods). we illustrate the technique with a representative example.
algorithmic analysis of a basic evolutionary algorithm for continuous optimization. in practical optimization, applying evolutionary algorithms has nearly become a matter of course. their theoretical analysis, however, is far behind practice. so far, theorems on the runtime are limited to discrete search spaces; results for continuous search spaces are limited to convergence theory or even rely on validation by experiments, which is unsatisfactory from a theoretical point of view. the simplest, or most basic, evolutionary algorithms use a population consisting of only one individual and use random mutations as the only search operator. here the so-called (1+1) evolution strategy for minimization in r^n is investigated when it uses isotropically distributed mutation vectors. in particular, so-called gaussian mutations are analyzed when the so-called 1/5-rule is used for their adaptation. obviously, a reasonable analysis must respect the function to be minimized, and furthermore, the runtime must be measured with respect to the approximation error. a first algorithmic analysis of how the runtime depends on n, the dimension of the search space, is presented. this analysis covers all unimodal functions that are monotone with respect to the distance from the optimum. it turns out that, in the scenario considered, gaussian mutations in combination with the 1/5-rule indeed ensure asymptotically optimal runtime; namely, @q(n) steps/function evaluations are necessary and sufficient to halve the approximation error.
map construction of unknown graphs by multiple agents. we consider a distributed version of the graph exploration and mapping problem where a mobile agent has to traverse the edges of an unlabelled (i.e., anonymous) graph and return to its starting point, building a map of the graph in the process. in our case, instead of a single agent, there are k identical (i.e., mutually indistinguishable) agents initially dispersed among the n nodes of the graph. the agents can communicate by writing to the small public bulletin boards available at each node. the objective is for each agent to build an identically labelled map of the graph; we call this the labelled map construction problem. this problem is much more difficult than exploration by a single agent, because it involves achieving cooperation among multiple agents. in fact, this problem is deterministically unsolvable in some cases. we present deterministic algorithms that successfully and efficiently solve the problem under the condition that the values of n and k are co-prime with each other. we also show how the problem of labelled map construction is related to other problems like leader election and rendezvous of agents.
efficient pebbling for list traversal synopses with application to program rollback. we show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. using o(lgn) memory for a list of size n, the i'th back-step from the farthest point reached so far takes o(lgi) time in the worst case, while the overhead per forward step is at most @e for arbitrary small constant @e>0. an arbitrary sequence of forward and back steps is allowed. a full trade-off between memory usage and time per back-step is presented: k vs. kn^1^/^k and vice versa. our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n^1^/^k-ary, tree that can only be traversed in a pre-order fashion. the compact data structures used by the pebbling algorithms, called list traversal synopses, extend to general directed graphs, and have other interesting applications, including memory efficient hash-chain implementation. perhaps the most surprising application is in showing that for any program, arbitrary rollback steps can be efficiently supported with small overhead in memory, and marginal overhead in its ordinary execution. more concretely: let p be a program that runs for at most t steps, using memory of size m. then, at the cost of recording the input used by the program, and increasing the memory by a factor of o(lgt) to o(mlgt), the program p can be extended to support an arbitrary sequence of forward execution and rollback steps: the i'th rollback step takes o(lgi) time in the worst case, while forward steps take o(1) time in the worst case, and 1+@e amortized time per step.