Fundamenta Informaticae - Volume 155, issue 1-2

Authors: Durand-Lose, Jérôme | Kari, Jarkko | Nagy, Benedek

Article Type: Editorial

DOI: 10.3233/FI-2017-1573

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. v-vii, 2017

Authors: Janicki, Ryszard | Kleijn, Jetty | Koutny, Maciej | Mikulski, Łukasz

Article Type: Research Article

Abstract: A step trace is an equivalence class of step sequences which can be thought of as different observations of the same underlying concurrent history. Equivalence is determined on basis of a step alphabet that describes the relations between events in terms of potential simultaneity and sequentialisability. Step traces cannot be represented by standard partial orders, but require so-called invariant structures, extended order structures that capture the phenomena of mutual exclusion and weak causality. In this paper, we present an effective way of deciding whether an invariant structure represents a step trace over a given step alphabet. We also describe …a method by which one can check whether a given invariant structure can represent a step trace over any step alphabet. Moreover, if the answer is positive, the method provides a suitable step alphabet. Show more

Keywords: step trace, step alphabet, dependence graph, partial order, invariant structure, simultaneity, serialisability, sequentialisability, interleaving, mutual exclusion, synthesis

DOI: 10.3233/FI-2017-1574

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 1-29, 2017

Authors: Kutrib, Martin | Wendlandt, Matthias

Article Type: Research Article

Abstract: A k -limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where k ≥ 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k -limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all k ≥ 0, sweeping k -limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. …Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and k + 3 rewrite operations. We investigate closure properties of the family of languages accepted by reversible k -limited automata. It turns out that these families are not closed under intersection, but are closed under complementation. They are closed under intersection with regular languages, which leads to the non-closure under concatenation, iteration, and homomorphisms. Finally, it turns out that all k -limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages. Show more

DOI: 10.3233/FI-2017-1575

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 31-58, 2017

Authors: Kutrib, Martin | Malcher, Andreas | Wendlandt, Matthias

Article Type: Research Article

Abstract: In input-driven automata the input alphabet is divided into distinct classes and different actions on the storage medium are solely governed by the input symbols. For example, in input-driven pushdown automata (IDPDA) there are three distinct classes of input symbols determining the action of pushing, popping, or doing nothing on the pushdown store. Here, input-driven automata are extended in such a way that the input is preprocessed by a deterministic sequential transducer. IDPDAs extended in this way are called tinput-driven pushdown automata (TDPDA) and it turns out that TDPDAs are more powerful than IDPDAs but still not as powerful as …real-time deterministic pushdown automata. Nevertheless, even this stronger model has still good closure and decidability properties. In detail, it is shown that TDPDAs are closed under the Boolean operations union, intersection, and complementation. Furthermore, decidability procedures for the inclusion problem as well as for the questions of whether a given automaton is a TDPDA or an IDPDA are developed. Additionally, representation theorems for the context-free languages using IDPDAs and TDPDAs are established. Two other classes investigated are on the one hand TDPDAs restricted to tinput-driven counter automata and on the other hand TDPDAs generalized to tinput-driven stack automata. In both cases, it is possible to preserve the good closure and decidability properties of TDPDAs, namely, the closure under the Boolean operations as well as the decidability of the inclusion problem. Show more

DOI: 10.3233/FI-2017-1576

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 59-88, 2017

Authors: Drewes, Frank | Holzer, Markus | Jakobi, Sebastian | van der Merwe, Brink

Article Type: Research Article

Abstract: We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. BERGLUND , et al.: Cuts in regular expressions. In Proc . DLT , LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n –1)·m +n states, otherwise, on DFAs accepting the cut of two individual languages that are …accepted by n - and m -state DFAs, respectively. In the unary case we obtain max(2n –1,m +n –2) states as a tight bound—notice that for m ≤ n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n -state DFA we find a matching bound of 1+(n +1) · F(1,n +2,–n +2;n +1 | –1) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n – 1)!). Finally, the bound drops to 2n – 1 for unary DFAs accepting the iterated cut of an n -state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs. Show more

Keywords: finite automata, cut and iterated cut operation, descriptional complexity

DOI: 10.3233/FI-2017-1577

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 89-110, 2017

Authors: Csuhaj-Varjú, Erzsébet | Freund, Rudolf | Vaszil, György

Article Type: Research Article

Abstract: In this paper we establish a connection between two concepts of unconventional computing, namely Watson-Crick T0L systems (schemes) and red-green Turing machines or red-green register machines. Our research was inspired by the conceptual similarity of a mind change of a red-green Turing or register machine and of a turn to the complementary string in Watson-Crick T0L systems as well as by the fact that both red-green Turing or register machines and Watson-Crick T0L systems define infinite computations on finite inputs. We define language recognition for Watson-Crick T0L systems based on the infinite sequences they generate, and we show …that the sets of (vectors of) natural numbers which can be recognized by so-called standard Watson-Crick T0L schemes (with a context-free trigger) include the sets recognized by red-green register machines (or red-green Turing machines). The obtained results imply that using Watson-Crick T0L schemes we may “go beyond Turing” as the red-green register machines and red-green Turing machines can do. Furthermore, we also show that for any deterministic Watson-Crick 0L scheme with a regular trigger the recognizability problem of a word is decidable. Show more

Keywords: complementary relation, mind change, red-green register machines, red-green Turing machines, Watson-Crick T0L systems

DOI: 10.3233/FI-2017-1578

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 111-129, 2017

Authors: Hendricks, Jacob | Patitz, Matthew J. | Rogers, Trent A.

Article Type: Research Article

Abstract: In this paper, we extend existing results about simulation and intrinsic universality in a model of tile-based self-assembly. Namely, we work within the 2-Handed Assembly Model (2HAM), which is a model of self-assembly in which assemblies are formed by square tiles that are allowed to combine, using glues along their edges, individually or as pairs of arbitrarily large assemblies in a hierarchical manner, and we explore the abilities of these systems to simulate each other when the simulating systems have a higher “temperature” parameter, which is a system wide threshold dictating how many glue bonds must be formed between two …assemblies to allow them to combine. It has previously been shown that systems with lower temperatures cannot simulate arbitrary systems with higher temperatures, and also that systems at some higher temperatures can simulate those at particular lower temperatures, creating an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. These previous results relied on two different definitions of simulation, one (strong simulation) seemingly more restrictive than the other (standard simulation), but which have previously not been proven to be distinct. Here we prove distinctions between them by first fully characterizing the set of pairs of temperatures such that the high temperature systems are intrinsically universal for the lower temperature systems (i.e. one tile set at the higher temperature can simulate any at the lower) using strong simulation. This includes the first impossibility result for simulation downward in temperature. We then show that lower temperature systems which cannot be simulated by higher temperature systems using the strong definition, can in fact be simulated using the standard definition, proving the distinction between the types of simulation. Show more

DOI: 10.3233/FI-2017-1579

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 131-162, 2017

Authors: Ivanov, Sergiu | Verlan, Sergey

Article Type: Research Article

Abstract: In this article, we consider leftist insertion-deletion systems (LIDS), in which all rules have contexts on the same (left) side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fixed words. We prove that in this case the computational completeness is achieved when additional control mechanisms are used (graph control with two states, matrix control with binary matrices and random-context control). We then show how rules with regular contexts can be simulated by conventional rules checking one-symbol (resp. two-symbol) left …contexts for insertion and two-symbol (resp. one-symbol) left contexts for deletion. This simulation does not generally hold in the controlled case, however. Hence, we provide a construction simulating an arbitrary 2-tag system using extended rules and which can be rewritten in terms of conventional rules of types above, which implies that the latter systems are universal. Show more

DOI: 10.3233/FI-2017-1580

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 163-185, 2017

Authors: Nagy, Benedek | Vályi, Sándor

Article Type: Research Article

Abstract: Interval-valued computing is a new computing paradigm that is based on manipulations of interval-values. Interval-values are finite unions of intervals on the unit interval [0, 1) so this kind of computing can be considered as a continuous space machine like optical computing [25]. Based on the massive parallelism of this paradigm, various intractable problems can be solved efficiently, i.e., by polynomial number of steps. In this paper, the well-known complexity classes, NP and coNP are addressed. A specific subclass of polynomial size interval-valued computations is proven to characterize NP , that is, exactly languages with non-deterministically polynomial time …complexity can be decided by interval-valued computations of this subclass. This specific subclass of interval-valued computations does not use any of the shift operators, moreover the product operator is used only in the starting section of the computation. Due to the fact that interval-valued computing is a deterministic model of computing, an analogue result can be established for the class coNP . Show more

Keywords: new computing paradigms, unconventional computing, interval-valued computing, complexity, NP, coNP, massive parallelism, deterministic computing

DOI: 10.3233/FI-2017-1581

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 187-207, 2017

Authors: Fernau, Henning | Freund, Rudolf | Siromoney, Rani | Subramanian, K.G.

Article Type: Research Article

Abstract: We consider the external variant of non-isometric d -dimensional contextual array grammars with regular control together with local selectors allowing for controlling how d -dimensional arrays are evolving by adjoining rectangular (d –1)-dimensional arrays. In the 1-dimensional case, the computational power of these non-isometric contextual array grammars with regular control and local selectors equals the computational power of isometric contextual array grammars with regular control. The string images of the languages of 1-dimensional arrays generated by these contextual array grammars exactly yield the linear languages. In the more-dimensional case, non-isometric d -dimensional contextual array grammars with regular control and local …selectors can simulate the computations of (d – 1)-dimensional array grammars or Turing machines. Hence, for example, the emptiness problem for non-isometric d -dimensional contextual array grammars with regular control and local selectors for d > 1 is undecidable. We also compare the computational power of all variants of non-isometric d -dimensional contextual array grammars that we introduce to each other. Show more

Keywords: Array languages, isometric versus non-isometric variants, contextual grammars

DOI: 10.3233/FI-2017-1582

Citation: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 209-232, 2017