Fundamenta Informaticae - Volume 74, issue 4

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