Fundamenta Informaticae - Volume 74, issue 4

Authors: Margenstern, Maurice

Article Type: Other

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. i-ii, 2006

Authors: Alhazov, Artiom | Freund, Rudolf | Leporati, Alberto | Oswald, Marion | Zandron, Claudio

Article Type: Research Article

Abstract: We introduce a new variant of membrane systems where the rules are directly assigned to membranes and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for systems working in the sequential mode with a kind of priority relation on the rules we …already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. On the other hand, when using the maximally parallel mode, we do not need a priority relation to obtain computational completeness. Finally, we introduce the corresponding model of tissue P systems with energy assigned to the membrane of each cell and objects moving from one cell to another one in the environment as well as being able to change the energy of a cell when entering or leaving the cell. In each derivation step, only one object may pass through the membrane of each cell. When using priorities on the rules in the sequential mode (where in each derivation step only one cell is affected) as well as without priorities in the maximally parallel mode (where in each derivation step all cells possible are affected) we again obtain computational completeness, whereas without priorities on the rules in the sequential mode we only get a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. Show more

Keywords: computational completeness, matrix grammars, membrane computing, P systems

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 391-408, 2006

Authors: Bournez, Olivier | Hainry, Emmanuel

Article Type: Research Article

Abstract: Recently, using a limit schema, we presented an analog and machine independent algebraic characterization of elementary functions over the real numbers in the sense of recursive analysis. In a different and orthogonal work, we proposed a minimalization schema that allows to provide a class of real recursive functions that corresponds to extensions of computable functions over the integers. Mixing the two approaches we prove that computable functions over the real numbers in the sense of recursive analysis …can be characterized as the smallest class of functions that contains some basic functions, and closed by composition, linear integration, minimalization and limit schema. Show more

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 409-433, 2006

Authors: Burderi, Fabio | Castiglione, Giuseppa | Restivo, Antonio

Article Type: Research Article

Abstract: In this paper we investigate properties of different classes of discrete sets with respect to the partial-order of subpicture. In particular we take in consideration the classes of convex polyominoes and L-convex polyominoes. In the first part of the paper we study closure properties of these classes with respect the order and we give a new characterization of L-convex polyominoes. In the second part we pose the question to extend Higman's theoremto discrete sets. We give …a negative answer in the general case and we prove that the set of L-convex polyominoes is well-partially-ordered by using a representation of L-convex polyominoes in terms of words of a regular language. Show more

Keywords: Discrete sets, polyominoes and L-convex polyominoes, subpicture order and well-partial-ordering

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 435-446, 2006

Authors: Cavaliere, Matteo | , Peter | Leupold,

Article Type: Research Article

Abstract: Models of computation in theoretical computer science very frequently consist of a device performing some type of process, like a Turing machine and its computation or a grammar and its derivation. After the process halts, only some final output is regarded as the result. In adding an observer to such a device, one can obtain a protocol of the entire process and then use this as the result of the computation. In several recent articles this approach …has proved to often exceed greatly the power of the observed system. Here we apply this architecture to string-rewriting systems. They receive a string as input, and a combination of observer and decider then determines whether this string is accepted. This decision is based only on the rewriting process performed. First we determine the power of painter, context-free, and inverse context-free rewriting systems in terms of McNaughton languages. Then these are investigated as components of rewriting/observer systems, and we obtain characterizations of the classes of context-sensitive and recursively enumerable languages. Finally we investigate some limitations, i.e. characterize some systems, where observation does not increase power. Show more

Keywords: String-Rewriting, McNaughton Languages, Observation

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 447-462, 2006

Authors: Delvenne, Jean-Charles | Kůrka, Petr | Blondel, Vincent

Article Type: Research Article

Abstract: Many different definitions of computational universality for various types of dynamical systems have flourished since Turing's work. We propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. Universality of a system is defined as undecidability of a model-checking problem. For Turing machines, counter machines and tag systems, our definition coincides with the classical one. It yields, however, a new definition for cellular automata and subshifts. Our …definition is robust with respect to initial condition, which is a desirable feature for physical realizability. We derive necessary conditions for undecidability and universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have infinite number of subsystems. We also discuss the thesis according to which computation should occur at the 'edge of chaos' and we exhibit a universal chaotic system. Show more

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 463-490, 2006

Authors: Durand-Lose, Jérôme

Article Type: Research Article

Abstract: The Black hole model of computation provides super-Turing computing power since it offers the possibility to decide in finite (observer's) time any recursively enumerable (R.E.) problem. In this paper, we provide a geometric model of computation, conservative abstract geometrical computation, that, although being based on rational numbers (and not real numbers), has the same property: it can simulate any Turing machine and can decide any R.E. problem through the creation of an accumulation. Finitely many signals …can leave any accumulation, and it can be known whether anything leaves. This corresponds to a black hole effect. Show more

Keywords: Abstract geometrical computation, Black hole model, Energy conservation, Malament-Hogarth space-time, Super-Turing computation, Turing universality, Zeno phenomena

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 491-510, 2006

Authors: Holzer, Markus | Kutrib, Martin

Article Type: Research Article

Abstract: The number of registers or variables of a LOOP-, WHILE-, or GOTO-program, needed to compute a certain (partial) function from non-negative integers into non-negative integers, is a natural measure of complexity. We show that the hierarchy of LOOP-computable (WHILE-, and GOTO-computable, respectively) functions f: N→N (partial functions f: N↪N, respectively) which is induced by the number of registers collapses to level four (three, respectively). So, there exist universal WHILE- and GOTO-programs with …a constant number of registers. In all three cases we give a characterization of the functions that can be computed by one register only. These characterizations are used to show that the first levels of the register hierarchies are strict, and to compare these levels. Surprisingly, for total functions it turns out that the bottom level of the LOOP-hierarchy is incompa-rable (with respect to set inclusion) to the bottom levels of the WHILE- and GOTO-hierarchies. Finally we briefly discuss the impact of the register operations on the presented results. Show more

Keywords: Computability theory, Programming approach to computability, LOOP-,WHILE-, and GOTO-programs, Register Complexity

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 511-528, 2006

Authors: Leporati, Alberto | Zandron, Claudio | Mauri, Giancarlo

Article Type: Research Article

Abstract: We introduce energy-based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. Basing upon the seminal paper of Fredkin and Toffoli on conservative logic, we first show how energy-based P systems can be used to simulate the Fredkin gate, a reversible and conservative three-input/three-output boolean gate which is functionally complete for boolean logic. Then, we show how any reversible Fredkin …circuit can be simulated by energy-based P systems whose number of membranes is independent of the number of gates occurring in the simulated circuit. The simulating P systems turn out to be themselves reversible and conservative. Show more

Keywords: Energy-based P systems, reversible Fredkin circuits

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 529-548, 2006

Authors: Néraud, Jean

Article Type: Research Article

Abstract: Let M be a submonoid of the free monoid A*, and let X⊂M be a variable length code (for short a code). X is weakly M-complete if and only if any word in M is a factor of some word in X* (cf [20]). In this paper, which is the full version of a result presented in [17], we are interested by an effective computation of a weakly M-complete code containing X, namely �⊂M. In this framework, we consider the …class of submonoids M of A* which have finite rank. We define the rank of M as the rank of the minimal automaton with behavior M, i.e. the smallest positive integer r such that a word w satisfies ∣Q·w∣=r, where Q stands for the set of states (the action of the word w may be not defined on some state in Q). Regular submonoids are the most typical example of submonoids with finite rank. Given a submonoid with finite rank M⊂A*, and given a code X⊂M, we present a method of completion which makes only use of regular or boolean operations on sets. As a consequence, if M and X are regular sets then so is �. Show more

Keywords: Words, free monoid, submonoid, variable length code, minimal automaton, rank, den-sity, completeness, local density, weakly complete, strongly thin, completable, completion of a code

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 549-562, 2006

Authors: Okhotin, Alexander

Article Type: Research Article

Abstract: It has recently been shown that several computational models, such as trellis automata, recursive functions and Turing machines, admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is proved that the universality and the associated hardness of decision problems begins at one-variable equations. Additionally, it …is shown that language equations with added quotient with regular languages can specify every set representable in first-order Peano arithmetic. Show more

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 563-578, 2006

Authors: Schott, René | Spehner, Jean-Claude

Article Type: Research Article

Abstract: The shuffle of k words u_1 ,…,u_k is the set of words obtained by interleaving the letters of these words such that the order of appearance of all letters of each word is respected. The study of the shuffle product of words leads to the construction of an automaton whose structure is deeply connected to a family of trees which we call araucarias. We prove many structural properties of this family of trees …and give some combinatorial results. We introduce a family of remarkable symmetrical polynomials which play a crucial role in the computation of the size of the araucarias. We prove that the minimal partial automaton which recognizes the shuffle of a finite number of special words contains an araucaria for each integer k>0. Show more

Keywords: Automaton, shuffle of words, remarkable polynomials, trees

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 579-601, 2006

Authors: Umeo, Hiroshi | Maeda, Masashi | Hisaoka, Masaya | Teraoka, Masato

Article Type: Research Article

Abstract: A simple and state-efficient mapping scheme is proposed for embedding any one-dimensional (1-D) firing squad synchronization algorithm onto two-dimensional (2-D) arrays, and some new 2-D synchronization algorithms based on the mapping scheme are presented. The proposed mapping scheme can be readily applied to the design of 2-D synchronization algorithms with fault tolerance, algorithms operating on multi-dimensional cellular arrays, and for the generalized case where the general is located at an arbitrary position on the …2-D array. First a six-state algorithm is developed that can synchronize any m×n rectangular array in 2(m+n)−4 steps. Then, a fourteen-state generalized algorithm is also developed that can synchronize any m×n rectangular array with the general at an arbitrary initial position (r,s) in m+n+max(r+s,m+n−r−s+2)−4 steps. The latter algorithm is interesting in that it includes a new optimum-time synchronization algorithm as a special case where the general is located at one corner. We progressively reduce the number of internal states of each cellular automaton on rectangular arrays, achieving six states and fourteen states for a rectangular array in non-optimum and optimum-time complexities, respectively. These are the smallest number of states reported to date for synchronizing rectangular arrays. Show more

Keywords: cellular automaton, firing squad synchronization algorithm, fault-tolerant synchronization algorithm

Citation: Fundamenta Informaticae, vol. 74, no. 4, pp. 603-623, 2006