984 research outputs found
On the structure of solution sets to regular word equations
No full text© Joel D. Day and Florin Manea; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). For quadratic word equations, there exists an algorithm based on rewriting rules which generates a directed graph describing all solutions to the equation. For regular word equations - those for which each variable occurs at most once on each side of the equation - we investigate the properties of this graph, such as bounds on its diameter, size, and DAG-width, as well as providing some insights into symmetries in its structure. As a consequence, we obtain a combinatorial proof that the problem of deciding whether a regular word equation has a solution is in NP
A series of algorithmic results related to the iterated hairpin completion
No full textAbstractIn this paper we propose efficient algorithmic solutions for the computation of the hairpin completion distance between two given words, for the computation of a minimum-distance common hairpin completion ancestor of two given words (i.e., a word from which we can obtain the two given words by iterated hairpin completion, such that the sum of the hairpin completion distances from this word to the two given words is minimum), and, respectively, for the computation of an arbitrary hairpin completion ancestor of two given words. In all the cases we improve the upper bounds known for time complexity of solving these problems. Then we show how the algorithms designed for these three initial problems can be modified to solve a series of related problems
Complexity results for deciding Networks of Evolutionary Processors
No full textAbstractThe Accepting Networks of Evolutionary Processors (ANEPs for short) are bio-inspired computational models which were introduced and thoroughly studied in the last decade. In this paper we propose a method of using ANEPs as deciding devices. More precisely, we define a new halting condition for this model, which seems more coherent with the rest of the theory than the previous such definitions, and show that all the computability related results reported so far remain valid in the new framework. Further, we are able to show a direct and efficient simulation of an arbitrary ANEP by an ANEP having a complete underlying graph; as a consequence of this result, we conclude that the efficiency of deciding a language by ANEPs is not influenced by the network’s topology. Finally, focusing on the computational complexity of ANEP-based computations, we obtain a surprising characterisation of PNP[log] as the class of languages that can be decided in polynomial time by such networks
On the recognition of context-free languages using accepting hybrid networks of evolutionary processors
No full textOn Turing Machines Deciding According to the Shortest Computations
No full textIn this paper we propose and analyse from the computational complexity point of view several new variants of nondeterministic Turing machines. In the first such variant, a machine accepts a given input word if and only if one of its shortest possible computations on that word is accepting; on the other hand, the machine rejects the input word when all the shortest computations performed by the machine on that word are rejecting. We are able to show that the class of languages decided in polynomial time by such machines is PNP[log]. When we consider machines that decide a word according to the decision taken by the lexicographically first shortest computation, we obtain a new characterization of PNP. A series of other ways of deciding a language with respect to the shortest computations of a Turing machine are also discussed
Freeness of partial words
No full textAbstractThe paper approaches the classical combinatorial problem of freeness of words, in the more general case of partial words. First, we propose an algorithm that tests efficiently whether a partial word is k-free or not, for a given k. Then, we show that there exist arbitrarily many k-free infinite partial words, over a binary alphabet, containing an infinite number of holes, for k≥3. Moreover, we present an efficient algorithm for the construction of a cube-free partial word with a given number of holes, over a binary alphabet. In the final section of the paper, we show that there exists an infinite word, over a four-symbol alphabet, in which we can substitute randomly one symbol with a hole, and still obtain a cube-free word; we show that such a word does not exist for alphabets with fewer symbols. Further, we prove that in this word we can replace arbitrarily many symbols with holes, such that each two consecutive holes are separated by at least two symbols, and obtain a cube-free partial word. This result seems interesting because any partial word containing two holes with less than two symbols between them is not cube-free. Finally, we modify the previously presented algorithm to construct, over a four-symbol alphabet, a cube-free partial word with exactly n holes, having minimal length, among all the possible cube-free partial words with at least n holes
All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary processors of constant size
No full textThe hardness of counting full words compatible with partial words
No full textAbstractWe present several problems regarding counting full words compatible with a set of partial words or with the factors of a partial word, and show that they are #P-complete. Some of these counting problems have NP-complete decision counterparts to which a hard variant of CNF-SAT is reduced parsimoniously; the rest are #P-complete problems that cannot be canonically associated to NP-complete decision problems. For these problems we assume that the set of symbols compatible with the wildcards equals the alphabet of the input partial word. When both a partial word and the cardinality of the alphabet compatible with the wildcard are given as input, we show that the central problem of counting the full words compatible with factors of the given partial word is also #P-complete. Finally, we propose a nontrivial exponential-time algorithm, working in polynomial space, useful to derive upper bounds for the time needed to solve the discussed problems
- …
