TY - JOUR A1 - Pablo Alarcon, Pedro A1 - Arroyo, Fernando A1 - Bordihn, Henning A1 - Mitrana, Victor A1 - Mueller, Mike T1 - Ambiguity of the multiple interpretations on regular languages JF - Fundamenta informaticae N2 - A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages. KW - Multiple interpretation scheme KW - regular language KW - o-ambiguity KW - internal ambiguity KW - external ambiguity Y1 - 2015 U6 - https://doi.org/10.3233/FI-2015-1200 SN - 0169-2968 SN - 1875-8681 VL - 138 IS - 1-2 SP - 85 EP - 95 PB - IOS Press CY - Amsterdam ER - TY - JOUR A1 - Bordihn, Henning A1 - Bottoni, Paolo A1 - Labella, Anna A1 - Mitrana, Victor T1 - Networks of picture processors as problem solvers JF - Soft Computing N2 - We propose a solution based on networks of picture processors to the problem of picture pattern matching. The network solving the problem can be informally described as follows: it consists of two subnetworks, one of them extracts at each step, simultaneously, all subpictures of identical (progressively decreasing) size from the input picture and sends them to the other subnetwork which checks whether any of the received pictures is identical to the pattern. We present an efficient solution based on networks with evolutionary processors only, for patterns with at most three rows or columns. Afterward, we present a solution based on networks containing both evolutionary and hiding processors running in O(n + m + kl) computational (processing and communication) steps, for any size (n, m) of the input pic-ture and (k, l) of the pattern. From the proofs of these results, we infer that any (k, l)-local language with 1 <= k <= 3 can be decided in O(n + m + l) computational steps by networks with evolutionary processors only, while any (k, l)-local language with arbitrary k, l can be decided in O(n + m + kl) computational steps by networks containing both evolutionary and hiding processors. KW - Picture KW - Picture processor KW - Hiding processor KW - Picture matching KW - (k,l)-Local language Y1 - 2016 U6 - https://doi.org/10.1007/s00500-016-2206-y SN - 1432-7643 SN - 1433-7479 VL - 21 SP - 5529 EP - 5541 PB - Springer CY - New York ER - TY - JOUR A1 - Bordihn, Henning A1 - Mitrana, Victor A1 - Negru, Maria C. A1 - Paun, Andrei A1 - Paun, Mihaela T1 - Small networks of polarized splicing processors are universal JF - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal N2 - In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. All these results can be obtained with NPSPs with valuations in the set as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of this simulation. KW - Computing with DNA KW - Splicing KW - Splicing processor KW - Polarization KW - 2-tag system KW - Turing machine Y1 - 2018 U6 - https://doi.org/10.1007/s11047-018-9691-0 SN - 1567-7818 SN - 1572-9796 VL - 17 IS - 4 SP - 799 EP - 809 PB - Springer CY - Dordrecht ER - TY - JOUR A1 - Bordihn, Henning A1 - Mitrana, Victor T1 - On the degrees of non-regularity and non-context-freeness JF - Journal of computer and system sciences N2 - We study the derivational complexity of context-free and context-sensitive grammars by counting the maximal number of non-regular and non-context-free rules used in a derivation, respectively. The degree of non-regularity/non-context-freeness of a language is the minimum degree of non-regularity/non-context-freeness of context-free/context-sensitive grammars generating it. A language has finite degree of non-regularity iff it is regular. We give a condition for deciding whether the degree of non-regularity of a given unambiguous context-free grammar is finite. The problem becomes undecidable for arbitrary linear context-free grammars. The degree of non-regularity of unambiguous context-free grammars generating non-regular languages as well as that of grammars generating deterministic context-free languages that are not regular is of order Omega(n). Context-free non-regular languages of sublinear degree of non-regularity are presented. A language has finite degree of non-context-freeness if it is context-free. Context-sensitive grammars with a quadratic degree of non-context-freeness are more powerful than those of a linear degree. KW - context-free grammar KW - degree of non-regularity KW - context-sensitive KW - grammar KW - degree of non-context-freeness Y1 - 2020 U6 - https://doi.org/10.1016/j.jcss.2019.09.003 SN - 0022-0000 SN - 1090-2724 VL - 108 SP - 104 EP - 117 PB - Elsevier CY - San Diego, Calif. [u.a.] ER - TY - JOUR A1 - Bordihn, Henning A1 - Mitrana, Victor A1 - Paun, Andrei A1 - Paun, Mihaela T1 - Hairpin completions and reductions BT - semilinearity properties JF - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal N2 - This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin completions or reductions of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying the non-iterated hairpin completion or hairpin reduction. A similar approach is then applied to the iterated variants of these operations. Along these lines, we define the hairpin reduction root of a language and show that the hairpin reduction root of a semilinear language is not necessarily semilinear except the universal language. A few open problems are finally discussed. KW - DNA hairpin formation KW - Hairpin completions KW - Hairpin reductions KW - Semilinearity property Y1 - 2020 U6 - https://doi.org/10.1007/s11047-020-09797-0 SN - 1572-9796 VL - 20 IS - 2 SP - 193 EP - 203 PB - Springer Science + Business Media B.V. CY - Dordrecht ER -