Fundamenta Informaticae - Volume 104, issue 1-2

Authors: Bordihn, Henning | Hirvensalo, Mika | Kutrib, Martin | Freund, Rudolf | Holzer, Markus | Otto, Friedrich

Article Type: Other

DOI: 10.3233/FI-2010-332

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. i-ii, 2010

Authors: Bianchi, Maria Paola | Palano, Beatrice

Article Type: Research Article

Abstract: We study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whether the induced event is d-periodic. These algorithms run in polynomial time whenever the MM-qfa given in input has complex amplitudes with rational components. We also characterize the recognition power of unary MM-qfa's, by proving that any unary regular language can be accepted by a MM-qfa with constant cut point and isolation. Yet, the amount of states of the resulting MM-qfa …is linear in the size of the corresponding minimal dfa. We also single out families of unary regular languages for which the size of the accepting MM-qfa's can be exponentially decreased. Show more

Keywords: Quantum automata, periodic events, unary languages

DOI: 10.3233/FI-2010-333

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 1-15, 2010

Authors: Černo, Peter | Mráz, František

Article Type: Research Article

Abstract: Restarting automata were introduced as a model for analysis by reduction, which is a linguistically motivated method for checking correctness of a sentence. We propose a new restricted version of restarting automata called clearing restarting automata with a very simple definition but simultaneously with interesting properties with respect to their possible applications. The new model can be learned very efficiently from positive examples and its stronger version can be used to learn effectively a large class of languages. We relate the class of languages recognized by clearing restarting automata to the Chomsky hierarchy.

Keywords: analysis by reduction, clearing restarting automata, formal languages, grammatical inference

DOI: 10.3233/FI-2010-334

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 17-54, 2010

Authors: Geffert, Viliam | Pighizzini, Giovanni | Mereghetti, Carlo

Article Type: Research Article

Abstract: We show that, for any ϵ > 0, there exists a language accepted in strong ϵ log n space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e., a 2-way nondeterministic Turing machine with one pebble that can be moved onto the input cells). Moreover, we provide optimal unary lower bounds on the product of space and input head reversals for strong and weak pebble machines accepting nonregular languages.

Keywords: computational complexity, space bounded computations, pebble machines, input head reversals

DOI: 10.3233/FI-2010-335

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 55-69, 2010

Authors: Leupold, Peter | Nagy, Benedek

Article Type: Research Article

Abstract: 5′ → 3′ WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that the expressive power of these automata increases with every additional run that they can make, both for deterministic and non-deterministic machines. This defines two incomparable infinite hierarchies of language classes between the regular and the context-sensitive languages. These hierarchies are complemented with classes defined by several restricted variants of 5′ → 3′ WK-automata like stateless automata. Finally we show that several standard problems …are undecidable for languages accepted by 5′ → 3′ WK-automata in only one run, for example the emptiness and the finiteness problems. Show more

Keywords: Automata, Formal Languages, Natural Computing, Watson-Crick Automata

DOI: 10.3233/FI-2010-336

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 71-91, 2010

Authors: Martín, Gema M. | Vico, Francisco J. | Dassow, Jüegen | Truthe, Bianca

Article Type: Research Article

Abstract: We extend the edit operators of substitution, deletion, and insertion of a symbol over a word by introducing two new operators (partial copy and partial elimination) inspired by biological gene duplication. We define a disruption measure for an operator over a word and prove that whereas the traditional edit operators are disruptive, partial copy and partial elimination are non-disruptive. Moreover, we show that the application of only edit operators does not generate (with low disruption) all the words over a binary alphabet, but this can indeed be done by combining partial copy and partial elimination with the substitution operator.

DOI: 10.3233/FI-2010-337

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 93-110, 2010

Authors: Masopust, Tomáš

Article Type: Research Article

Abstract: We continue the investigation of pushdown automata which are allowed to make a non-deterministic decision if and only if their pushdown content forms a string belonging to a given control language. We prove that if the control language is linear and non-regular, then the power of pushdown automata regulated in this way is increased to the power of Turing machines. From a practical point of view, however, it is inefficient to check the form of the pushdown content in each computational step. Therefore, we prove that only two checks of the pushdown content are of interest for these machines to …be computationally complete. Based on this observation, we introduce and discuss a new model of regulated pushdown automata. Show more

DOI: 10.3233/FI-2010-338

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 111-124, 2010

Authors: Nishio, Hidenosuke

Article Type: Research Article

Abstract: A new classification of arbitrary cellular automata (CA for short) in Zd is studied considering the set (group) of all permutations of the neighborhood ν and state set Q. Two CA (Zd , Q, fA , νA ) and (Zd , Q, fB , νB ) are called automorphisc, if there is a pair of permutations (π, �) of ν and Q, respectively, such that (fB , ν B ) = (�−1 fA π �, νA π ), where νπ denotes a permutation of ν and fπ denotes a permutation of arguments of local function f …corresponding to ν π . This automorphissm naturally induces a classification of CA, such that it generally preserves the global properties of CA up to permutation. As a typical example of the theory, the local functions of 256 ECA (1-dimensional 3-nearest neighbors 2-states CA) are classified into 46 classes. We also give a computer test of surjectivity, injecitivity and reversibility of the classes. Show more

Keywords: cellular automaton, automorphissm, classification, permutation, neighborhood, group action, ECA

DOI: 10.3233/FI-2010-339

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 125-140, 2010

Authors: Sutner, K.

Article Type: Research Article

Abstract: Cellular automata have rich computational properties and, at the same time, provide plausible models of physics-like computation. We study decidability issues in the phasespace of these automata, construed as automatic structures over infinite words. In dimension one, slightly more than the first order theory is decidable but the addition of an orbit predicate results in undecidability. We comment on connections between this “what you see is what you get” model and the lack of natural intermediate degrees.

DOI: 10.3233/FI-2010-340

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 141-160, 2010

Authors: Truthe, Bianca

Article Type: Research Article

Abstract: In this paper, a new definition of accepting networks – called target based accepting networks – is given. In a target based accepting network of evolutionary processors, each node is equipped with a target condition. As soon as a node contains a word which satisfies the target condition of that node, the input word is accepted by the network. In this way, no further output nodes are necessary. Regarding the communication in a network, we consider two cases of control: 1. input and output filters are regular languages, then the target conditions are to belong to certain regular languages, 2. …input and output filters are implemented as random context conditions, then the target conditions are given by sets of permitting and forbidding symbols. It is shown in both cases that conventional accepting networks and target based accepting networks have the same computational power. However, the number of processors needed for accepting a language can be reduced when using target based networks. Show more

Keywords: Networks of evolutionary networks, regular filters, random context filters, target based acceptance

DOI: 10.3233/FI-2010-341

Citation: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 161-183, 2010