There are ternary circular square-free words of length for 18.
There is no complete axiom system for shuffle expressions
There is no complete axiom system for shuffle expressions
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.
Threshold circuits for iterated matrix product and powering
Threshold Circuits for Iterated Matrix Product and Powering
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 .
Topological automata
Topological deformation of higher dimensional automata.
Tours de Hanoï et automates
Towards an integrated theory of formal and natural languages
Trace languages defined by regular string languages
Traces of term-automatic graphs
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...
Transcendental numbers having explicit -adic and Jacobi-Perron expansions
Transducteurs finis d'arbres et tests d'égalité
Transductions algébriques
Transductions des langages de Chomsky
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...
Transductions et familles de langages
Transductions rationnelles décroissantes
Transformations of grammars and translation directed by parsing
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...
Transformations of translation grammars
Translation from classical two-way automata to pebble two-way automata
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,...