There are ternary circular square-free words of length for 18.
Currie, James D. (2002)
The Electronic Journal of Combinatorics [electronic only]
A. Szepietowski (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
A. Szepietowski (2010)
RAIRO - Theoretical Informatics and Applications
In this paper we show that neither the set of all valid equations between shuffle expressions nor the set of schemas of valid equations is recursively enumerable. Thus, neither of the sets can be recursively generated by any axiom system.
Carlo Mereghetti, Beatrice Palano (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Carlo Mereghetti, Beatrice Palano (2010)
RAIRO - Theoretical Informatics and Applications
The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension matrices with integer or rational entries is studied. We call these two problems and , respectively, for short. We prove that: (i) For , does not belong to , unless .newline (ii) For stochastic matrices : belongs to while, for , does not belong to , unless . (iii) For any k, belongs to .
Hartmut Ehrig, Wolfgang Kühnel (1974)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Gaucher, Philippe, Goubault, Eric (2003)
Homology, Homotopy and Applications
J.-P. Allouche, F. Dress (1990)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Petr Jirků (1975)
Kybernetika
Ijsbrand Jan Aalbersberg, Emo Welzl (1986)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Antoine Meyer (2008)
RAIRO - Theoretical Informatics and Applications
In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state...
Jun-Ichi Tamura (1992)
Journal de théorie des nombres de Bordeaux
E. Lilin (1981)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Michel Fliess (1970)
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
Maurice Nivat (1968)
Annales de l'institut Fourier
La feuille des applications dites -transductions, et qu’il serait légitime d’appeler applications rationnelles, d’un monoïde libre dans un autre monoïde est étudiée de façon systématique. L’intérêt de ces applications vient de ce qu’elles transportent partie algébrique (ou -langages) sur partie algébrique, partie rationnelle (ou -langage) sur partie rationnelle. On étudie sous le nom de langage compilable les parties algébriques qu’une -transduction univoque applique dans un ensemble de Dyck...
Luc Boasson, Maurice Nivat (1971)
Mathématiques et Sciences Humaines
Jeannine Leguy (1981)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Bořivoj Melichar, Nguyen van Bac (2002)
Kybernetika
The class of translation grammars is introduced. This class is characterized by a possibility to implement a formal translation as an algorithm directed by parsing. To perform a translation, the conventional parser is extended by a facility to perform output operations within the parsing actions shift and reduce. The definitions of Kernel- and -translation grammars are presented. The transformations shaking-down and postponing that enable to transform some translation grammars into Kernel...
Bořivoj Melichar (1994)
Kybernetika
Viliam Geffert, L'ubomíra Ištoňová (2010)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles. However,...