waashk/dblp huggingface dataset:
on the computational complexity of membrane systems. we show how techniques in machine-based complexity can be used to analyze the complexity of membrane computing systems. we focus on catalytic syslems, communicating p systems, and systems with only symport/antiport rules, but our techniques are applicable to other p systems that are universal. we define space and time complexity measures and show hierarchies of complexity classes similar to well-known results concerning turing machines and counter machines. we also show that the deterministic communicating p system simulating a deterministic counter machine in (sosik (2002)) (pre-proc. of workshop on membrane computing (wmc-cdea2002), curtea de arges, romania, 2002, pp. 371-382), (sosik and matysek (2002)) (unconventional models of computation 2002, lecture notes in computer science, vol. 2509, springer, berlin, 2002, pp. 264-275.) can be constructed to have a fixed number of membranes, answering positively an open question in sosik (2002), sosik and matysek (2002). we prove that reachability of extended configurations for symport/antiport systems (as well as for catalytic systems and communicating p systems) can be decided in nondeterministic log n space and, hence, in deterministic log2 n space or in polynomial time, improving the main result in paun et al. (2002) (on the reachability problem for p systems with symport/antiport, 2002, submitted for publication.), we propose two equivalent systems that define languages (instead of multisets of objects): the first is a catalytic system language generator and the other is a communicating p system acceptor (or a symport/antiport system acceptor). these devices are universal and therefore can also be analyzed with respect to space and time complexity. finally, we give a characterization of semilinear languages in terms of a restricted form of catalytic system language generator.
on membrane hierarchy in p systems. we look at a restricted model of a communicating p system, called rcps, whose environment does not contain any object initially. the system can expel objects into the environment but only expelled objects can be retrieved from the environment. such a system is initially given an input a1i1 ... anin (with each ij representing the multiplicity of distinguished object ai, 1≤i≤n) and is used as an acceptor. we show that rcpss are equivalent to two-way multihead finite automata over bounded languages (i.e., subsets of a1* ... an*, for some distinct symbols a1 ..... an). we then show that there is an infinite hierarchy of rcps's in terms of the number of membranes: for every r, there is an s > r and a unary language l accepted by an rcps with s membranes that cannot be accepted by an rcps with r membranes. this provides an answer to an open problem in (membrane computing: an introduction, springer, berlin, 2002) which asks whether there is a nonuniversal model of a membrane computing system which induces an infinite hierarchy on the number of membranes. we also consider variants/generalizations of rcpss, e.g, acceptors of languages; models that allow a "polynomial bounded" supply of objects in the environment initially; models with tentacles, etc. we show that they also form an infinite hierarchy with respect to the number of membranes (or tentacles). the proof techniques can be used to obtain similar results for other restricted models of p systems, like symport/antiport systems.
on determinism versus nondeterminism in p systems. an important open problem in the area of membrane computing is whether there is a model of p systems for which the nondeterministic version is strictly more powerful than the deterministic version. we resolve this problem in the following sense--we exhibit two classes of p system acceptors with only communicating rules and show: 1. for the first class, the deterministic and nondeterministic versions are equivalent if and only if deterministic and nondeterministic linear bounded automata are equivalent. the latter problem is a long-standing open question in complexity theory. 2. for the second class, the deterministic version is strictly weaker than the nondeterministic version. both classes are nonuniversal, but can accept fairly complex languages.
eliminating the storage tape in reachability constructions. a discrete pushdown timed automaton is a pushdown machine with integer-valued clocks. it has been shown recently that the binary reachability of a discrete pushdown timed automaton can be accepted by a two-tape pushdown acceptor with reversal-bounded counters. we improve this result by showing that the stack can be eliminated from the acceptor, i.e., the binary reachability can be accepted by a two-tape finite-state acceptor with reversal-bounded counters. we calso obtain similar results for other machine models. our results can be used to verify certain properties concerning these machines that were not verifiable before using previous techniques. for example, we are able to formulate a subset of presburger ltl that is decidable for satisfiability checking with respect to these machines. we also discuss the "boundedness problem" for reachability sets. finally, we explain how the storage tape elimination technique can be applied to machines with real-valued clocks.
on two-way fa with monotonic counters and quadratic diophantine equations. we show an interesting connection between two-way deterministic finite automata with monotonic counters and quadratic diophantine equations. the automaton m operates on inputs of the form a1i1...anin for some fixed n and distinct symbols a1,...,an, where i1,...,in are nonnegative integers. we consider the following reachability problem: given a machine m, a state q, and a presburger relation e over counter values, is there (i1,...,in) such that m, when started in its initial state on the left end of the input a1i1...anin with all counters initially zero, reaches some configuration where the state is q and the counter values satisfy e? in particular, we look at the case when the relation e is an equality relation, i.e., a conjunction of relations of the form ci = cj. we show that this case and variations of it are equivalent to the solvability of some special classes of systems of quadratic diophantine equations. we also study the nondeterministic version of two-way finite automata augmented with monotonic counters with respect to the reachability problem. finally, we introduce a technique which uses decidability and undecidability results to show "separation" between language classes.
on the solvability of a class of diophantine equations and applications. for 1 ≤ i ≤ k, let ri denote pi(y)fi + gi, where pi(y) is a polynomial in y with integer coefficients, and fi, gi are linear polynomials in x1,..., xn with integer coefficients. let p(z1,..., zk) be a presburger relation over the nonnegative integers. we show that the following problem is decidable:given: r1,..., rk and a presburger relation p.question: are there nonnegative integer values for y, x1,..., xn such that for these values, (r1,..., rk) satisfies p? we also give some applications to decision problems concerning counter machines.
catalytic p systems, semilinear sets, and vector addition systems. we look at 1-region membrane computing systems which only use rules of the form ca → cv, where c is a catalyst, a is a noncatalyst, and v is a (possibly null) string of noncatalysts. there are no rules of the form a → v. thus, we can think of these systems as "purely" catalytic. we consider two types: (1) when the initial configuration contains only one catalyst, and (2) when the initial configuration contains multiple catalysts. we show that systems of the first type are equivalent to communication-free petri nets, which are also equivalent to commutative context-free grammars. they define precisely the semilinear sets. this partially answers an open question (in: wmc-cdea'02, lecture notes in computer science, vol. 2597, springer, berlin, 2003, pp. 400-409; computationally universal p systems without priorities: two catalysts are sufficient, available at http://psystems.disco.unimib.it, 2003). systems of the second type define exactly the recursively enumerable sets of tuples (i.e., turing machine computable). we also study an extended model where the rules are of the form q:(p, ca → cv) (where q and p are states), i.e., the application of the rules is guided by a finite-state control. for this generalized model, type (1) as well as type (2) with some restriction correspond to vector addition systems. finally, we briefly investigate the closure properties of catalytic systems.
verification in loosely synchronous queue-connected discrete timed automata. we look at a model of a queue system that consists of the following components: 1. two discrete timed automata w (the "writer") and r ("the reader"). 2. one unrestricted queue that can be used to send messages from w to r. there is no bound on the length of the queue. w and r do not share a global clock and operate in a loosely synchronous way. that is, the absolute value of the difference between the local time of w and the local time of r is always bounded by a positive constant. we show that the binary reachability for these systems is effectively computable, and this result is generalized to the case when there are two queues (one from w to r and the other from r to w) that operate in half-duplex. we then present some properties (e.g., safety, invariance, etc.) that can be verified for loosely synchronous queue-connected discrete timed automata and give an example of a system composed of a sensor and a controller that is verifiable using our results.
characterizations of context-sensitive languages and other language classes in terms of symport/antiport p systems. we give "syntactic" characterizations of context-sensitive languages (csls) in terms of some restricted models of symport/antiport p systems. these are the first such characterizations of csls in terms of p systems. in particular, we show the following for any language l over a binary alphabet: (1) let m be any integer ≥ 1. then l is a csl if and only if it can be accepted by a restricted symport/antiport p system with m membranes and multiple number of symbols (objects). moreover, holding the number of membranes at m, there is an infinite hierarchy in computational power (within the class of binary csls) with respect to the number of symbols. (2) let s be any integer ≥ 14. then l is a csl if and only if it can be accepted by a restricted symport/antiport p system with s symbols and multiple number of membranes. moreover, holding the number of symbols at s, there is an infinite hierarchy in computational power with respect to the number of membranes. (similar results hold for languages over an alphabet of k ≥ 2 symbols.) thus (1) and (2) say that in order for the restricted symport/antiport p systems to accept all binary csls, at least one parameter (either the number of symbols or the number of membranes) must grow. these are the first results of their kind in the p systems area. they contrast a known result that (unrestricted) symport/antiport p systems with s ≥ 2 symbols and m ≥ 1 membranes accept (or generate) exactly the recursively enumerable sets of numbers even for s + m = 6. we also note that previous characterizations of formal languages in the membrane computing literature are mostly for the parikh images of languages.variations of our model yield characterizations of regular languages, languages accepted by one-way log n space-bounded turing machines, and recursively enumerable languages.
on partially blind multihead finite automata. this work is concerned with 1-way multihead finite automata (fa), both deterministic and nondeterministic, in which the symbol under only one head controls its move. we call such a fa a partially blind multihead fa. we show some results regarding the decision problems and closure properties of blind multihead dfa and nfa. we also compare these devices with 1-way nfa augmented by reversal bounded counters. finally, we also present some results regarding the simulation of a partially blind dfa and nfa by a probabilistic finite automaton.
augmenting the discrete timed automaton with other data structures. we describe a general automata-theoretic approach for analyzing the verification problems of discrete timed automata (i.e., timed automata with integer-valued clocks) augmented with various data structures. formally, let c be a class of nondeterministic machines with reversal-bounded counters and possibly other data structures (e.g., a pushdown stack, a queue, a read-write work-tape, etc.). let a be a discrete timed automaton and m be a machine in b. denote by a ⊕ m the combined automaton, i.e., a augmented with m (in some precise sense to be defined). we show that if c has a decidable emptiness problem, then the (binary, forward, backward) reachability, safety, and invariance for a ⊕ m are solvable. we give examples of such c's and exhibit some new properties of discrete timed automata that can be verified. we also briefly consider reachability in discrete timed automata operating in parallel.
counter machines and verification problems. we study various generalizations of reversal-bounded multicounter machines and show that they have decidable emptiness, infiniteness, disjointness, containment, and equivalence problems. the extensions include allowing the machines to perform linear-relation tests among the counters and parameterized constants (e.g., "is 3x-5y-2d1 + 9d2 < 12?", where x, y are counters, and d1,d2 are parameterized constants). we believe that these machines are the most powerful machines known to date for which these decision problems are decidable. decidability results for such machines are useful in the analysis of reachability problems and the verification/debugging of safety properties in infinite-state transition systems. for example, we show that (binary, forward, and backward) reachability and safety are solvable for these machines.
deterministic catalytic systems are not universal. we look at a 1-membrane catalytic p system with evolution rules of the form ca → cv or a → v, where c is a catalyst, a is a noncatalyst symbol, and v is a (possibly null) string representing a multiset of noncatalyst symbols. (note that we are only interested in the multiplicities of the symbols.) a catalytic system (cs) can be regarded as a language acceptor in the following sense. given an input alphabet σ consisting of noncatalyst symbols, the system starts with an initial configuration wz, where w is a fixed string of catalysts and noncatalysts not containing any symbol in z, and z = a1n1...aknk for some nonnegative integers n1,..., nk, with (a1,...,ak) ⊆ σ. at each step, a maximal multiset of rules is nondeterministically selected and applied in parallel to the current configuration to derive the next configuration (note that the next configuration is not unique, in general). the string z is accepted if the system eventually halts.it is known that a 1-membrane cs is universal in the sense that any unary recursively enumerable language can be accepted by a 1-membrane cs (even by purely css, i.e., when all rules are of the form ca → cv). a cs is said to be deterministic if at each step there is a unique maximally parallel multiset of rules applicable. it has been an open problem whether deterministic systems of this kind are universal. we answer this question negatively. we show that the membership problem for deterministic css is decidable. in fact, we show that the parikh map of the language (⊆a1*...ak*) accepted by any deterministic cs is a simple semilinear set which can be effectively constructed. since nondeterministic 1-membrane cs acceptors (with two catalysts) are universal, our result gives the first example of a variant of p systems for which the nondeterministic version is universal, but the deterministic version is not.we also show that for a deterministic 1-membrane cs using only rules of type ca → cv, the set of reachable configurations from a given initial configuration is an effective semilinear set. the application of rules of type a → v, however, is sufficient to render the reachability set nonsemilinear. our results generalize to multimembrane deterministic css. we also consider deterministic css which allow rules to be prioritized and investigate three classes of such systems, depending on how priority in the application of the rules is interpreted. for these three prioritized systems, we obtain contrasting results: two are universal and one only accepts semilinear sets.
a generic type system for the pi-calculus. we propose a general, powerful framework of type systems for the π-calculus, and show that we can obtain as its instances a variety of type systems guaranteeing non-trivial properties like deadlock-freedom and race-freedom. a key idea is to express types and type environments as abstract processes: we can check various properties of a process by checking the corresponding properties of its type environment. the framework clarifies the essence of recent complex type systems, and it also enables sharing of a large amount of work such as a proof of type preservation, making it easy to develop new type systems.
on lengths of words in context-free languages. we consider slender languages, that is, languages for which the number of words of the same length is bounded from above by a constant. we prove that the slenderness problem is decidable for context-free languages and that the maximal number of words of the same length in a given context-free language is computable. some effective representations of slender context-free languages, as well as other related decidability problems are investigated.
on computational complexity of contextual languages. we consider the following restriction of internal contextual grammars, called local: in any derivation in a grammar, after applying a context, further contexts can be added only inside of or at most adjacent to the previous ones. we further consider a natural restriction of this derivation mode by requiring that no superword of the word considered as selector can be used as selector. we investigate the relevance of the latter type of grammars for natural language study. in this aim, we show that all the three basic non-context-free constructions in natural languages, that is, multiple agreements, crossed agreements, and duplication, can be realized using this type of grammars. our main result is that these languages are parsable in polynomial time. the problem of semilinearity remains open.
a generalization of repetition threshold. brandenburg and (implicitly) dejean introduced the concept of repetition threshold: the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. we generalize this concept to include the lengths of the avoided words. we give some conjectures supported by numerical evidence and prove some of these conjectures. as a consequence of one of our results, we show that the pattern abcbabc is 2-avoidable. this resolves a question left open in cassaigne's thesis.
on well quasi orders of free monoids. the paper investigates down-sets associated to well quasi orders. of particular language-theoretic interest is the quasi order $u\leq_s v$ (resp.$\!$ $u\leq_{\cp}v$) of $u$ being a subword (resp.$\!$ a parikh subword) of $v$, as well as their inverses. we establish a number of results about the regularity and effective regularity of the down-sets, in particular, a general condition for the effective regularity of the down-set associated to an inverse well quasi order (theorem 7.1). it is decidable whether or not an arbitrary regular language results as a down-set from an infinite or bi-infinite word, whereas the same problem is undecidable for context-free language. a quasi order being a well quasi order is connected to arbitrary languages being confluent.
reducing nfas by invariant equivalences. we give new general methods for constructing small non-deterministic finite automata (nfa) from arbitrary ones. given an nfa, we compute the largest right-invariant equivalence on the set of states and then merge the equivalent states to obtain a smaller automaton. when applying this method to position automata, we get a way to convert regular expressions into nfas which are always smaller than or equal to the position, partial derivative, and follow automata; it can be arbitrarily smaller. the construction can be dually made for left-invariant equivalences and then the two can be combined for even better results.
formal design and verification of operational transformation algorithms for copies convergence. distributed groupware systems provide computer support for manipulating objects such as a text document or a filesystem, shared by two or more geographically separated users. data replication is a technology to improve performance and availability of data in distributed groupware systems. indeed, each user has a local copy of the shared objects, upon which he may perform updates. locally executed updates are then transmitted to the other users. this replication potentially leads, however, to divergent (i.e. different) copies. in this respect, operational transformation (ot) algorithms are applied for achieving convergence of all copies, i.e. all users view the same objects. using these algorithms users can exchange their updates in any order since the convergence should be ensured in all cases. however, the design of such algorithms is a difficult and error-prone activity since building the correct updates for maintaining good convergence properties of the local copies requires examining a large number of situations. in this paper, we present the modelling and deductive verification of ot algorithms with algebraic specifications. we show in particular that many ot algorithms in the literature do not satisfy convergence properties unlike what was stated by their authors.
voronoi diagrams on piecewise flat surfaces and an application to biological growth. this paper introduces the notion of voronoi diagrams and delaunay triangulations generated by the vertices of a piecewise flat, triangulated surface. based on properties of such structures, a generalized flip algorithm to construct the delaunay triangulation and voronoi diagram is presented. an application to biological membrane growth modeling is then given. a voronoi partition of the membrane into cells is maintained during the growth process, which is driven by the creation of new cells and by restitutive forces of the elastic membrane.
some properties of one-pebble turing machines with sublogarithmic space. this paper investigates some aspects of the accepting powers of deterministic, nondeterministic, and alternating one-pebble turing machines with spaces between log log n and log n. we first investigate a relationship between the accepting powers of two-way deterministic one-counter automata and deterministic (or nondeterministic) one-pebble turing machines, and show that they are incomparable. then we investigate a relationship between nondeterminism and alternation, and show that there exists a language accepted by a strongly log log n space-bounded alternating one-pebble turing machine, but not accepted by any weakly o(log n) space-bounded nondeterministic one-pebble turing machine. finally, we investigate a space hierarchy, and show that for any one-pebble (fully) space constructible function l(n) ≤ log n, and for any function l'(n) = o(l(n)), there exists a language accepted by a strongly l(n) space-bounded deterministic one-pebble turing machine, but not accepted by any weakly l'(n) space-bounded nondeterministic one-pebble turing machine.