Inductive definitions in logic versus programs of real-time cellular automata
| Autor: | Grandjean, Etienne, Grente, Théo, Terrier, Véronique |
|---|---|
| Přispěvatelé: | Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Terrier, Véronique |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
descriptive complexity
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES computational complexity inductive logic cellular automata [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] [INFO]Computer Science [cs] [INFO] Computer Science [cs] real-time computation programming |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|