The paper deals with the class REC of recognizable picture languages, UREC its unambiguous variant and co-REC the complement class of REC. The aim of this paper is two-fold:First, the paper focuses ...on some necessary conditions for a language to be recognizable. Such conditions have already been identified in several works 1–5. Here, we revisit them in the light of communication complexity arguments.Second, we use communication complexity measures in order to construct a language which is a recognizable and co-recognizable language but not an unambiguous one. This answers a question raised in 6.
A poly-slender context-free language is a context-free language whose number of words of length n is polynomially bounded. Its structure has been thoroughly characterized by Ilie, Rozenberg and ...Salomaa. Thanks to this characterization, we show that every poly-slender context-free language is recognizable by a trellis automaton, if the languages of words with as many a as b and at most a constant number of alternations between a and b are recognizable by trellis automata. Then we construct a family of trellis automata that recognizes such languages.
Descriptive complexity provides intrinsic, i.e. machine-independent, characterizations of the main complexity classes. On the other hand, logic can be useful for designing programs in a natural ...declarative way. This is especially important for parallel computation models such as cellular automata, since designing parallel programs is considered a difficult task.
This paper establishes three logical characterizations of the three classical complexity classes modeling minimal time, called real-time, of one-dimensional cellular automata according to their canonical variations: unidirectional or bidirectional communication, input word given in a parallel or sequential way.
Our three logics are natural restrictions of existential second-order Horn logic with built-in successor and predecessor functions. These logics correspond exactly to the three ways of deciding a language on a square grid circuit of side n according to one of the three natural locations of an input word of length n: along a side of the grid, on the diagonal that contains the output cell – placed on the vertex (n,n) of the square grid–, or on the diagonal opposite to the output cell.
The key ingredient to our results is a normalization method that transforms a formula from one of our three logics into an equivalent normalized formula that closely mimics a grid circuit.
Then, we extend our logics by allowing a limited use of negation on hypotheses like in Stratified Datalog. By revisiting in detail a number of representative classical problems - recognition of the set of primes by Fisher's algorithm, Dyck language recognition, Firing Squad Synchronization problem, etc. - we show that this extension makes easier programming and we prove that it does not change the real-time complexity of our logics.
Finally, based on our experience in expressing these representative problems in logic, we argue that our logics are high-level programming languages: they make it possible to express in a natural, complete and synthetic way the algorithms of the literature, based on signals – and even to design new inductive algorithms –, and to translate them automatically into cellular automata of the same complexity.
In this paper, multidimensional cellular automaton are considered. We investigate the hierarchy designed by the low complexity classes when the dimensionality is increased. Whether this hierarchy is ...strict, is an open problem. However, we compare different variants and study their closure properties. We present also a correspondence between a main variant of multidimensional real-time cellular automata and one-way multihead alternating finite automata.
We present a relationship between two major models of parallel computation: the one-way cellular automata and the boolean circuits. The starting point is the boolean circuit of small depth designed ...by Ladner and Fischer to simulate any rational transducer. We extend this construction to simulate one-way cellular automata by boolean circuits.
Concerning the power of one-dimensional cellular automata recognizers, Ibarra and Jiang have proved that real time cellular automata (CA) and linear time CA are equivalent if and only if real time CA ...is closed under reverse. In this paper we investigate the question of equality of real time CA and linear time CA with respect to the operations of concatenation and cycle. In particular, we prove that if real time CA is closed under concatenation then real time CA is as powerful as linear time CA on the unary languages. We also prove that the question of knowing whether real time CA is as powerful than linear time CA is equivalent to the question of whether real time CA is closed under cycle. Moreover, in the case of two-dimensional CA recognizers, we investigate how restricted communication reduces the computational power. In particular, we show that real time CA and linear time CA with restricted variants of Moore and Von Neumann neighborhoods are not closed under rotation. Furthermore, they are not equivalent to real time CA with Moore or Von Neumann neighborhoods.
Descriptive complexity provides intrinsic, that is,machine-independent, characterizations of the major complexity classes. On the other hand, logic can be useful for designing programs in a natural ...declarative way. This is particularly important for parallel computation models such as cellular automata, because designing parallel programs is considered a difficult task.This paper establishes three logical characterizations of the three classical complexity classes modeling minimal time, called real-time, of one-dimensional cellular automata according to their canonical variants: unidirectional or bidirectional communication, input word given in a parallel or sequential way.Our three logics are natural restrictions of existential second-order Horn logic with built-in successor and predecessor functions. These logics correspond exactly to the three ways of deciding a language on a square grid circuit of side n according to one of the three canonical locations of an input word of length n: along a side of the grid, on the diagonal that contains the output cell, or on the diagonal opposite to the output cell.The key ingredient of our results is a normalization method that transforms a formula from one of our three logics into an equivalent normalized formula that faithfully mimics a grid circuit.Then, we extend our logics by allowing a limited use of negation on hypotheses like in Stratified Datalog. By revisiting in detail a number of representative classical problems - recognition of the set of primes by Fisher’s algorithm, Dyck language recognition, Firing Squad Synchronization problem,etc. - we show that this extension makes easier programming and we prove that it does not change the complexity of our logics in real-time.Finally, starting from our experience in expressing those representative problems in logic, we argue that our logics are high-level programming languages: they allow to express in a natural,precise and synthetic way the algorithms of literature, based on signals, and to translate them automatically into cellular automata of the same complexity.
Linear functional classes over cellular automata Grandjean, Anaël; Richard, Gaétan; Terrier, Véronique
Electronic proceedings in theoretical computer science,
08/2012, Letnik:
90, Številka:
Proc. AUTOMATA&JAC 2012
Journal Article
Odprti dostop
Cellular automata are a discrete dynamical system which models massively parallel computation. Much attention is devoted to computations with small time complexity for which the parallelism may ...provide further possibilities. In this paper, we investigate the ability of cellular automata related to functional computation. We introduce several functional classes of low time complexity which contain "natural" problems. We examine their inclusion relationships and emphasize that several questions arising from this functional framework are related to current ones coming from the recognition context. We also provide a negative result which explicits limits on the information transmission whose consequences go beyond the functional point of view.
PDF
