EuDML | Browse

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3 Next

Displaying 41 – 60 of 75

There are ternary circular square-free words of length $n$ for $n \geq$ 18.

Currie, James D. (2002)

The Electronic Journal of Combinatorics [electronic only]

There is no complete axiom system for shuffle expressions

A. Szepietowski (1999)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

There is no complete axiom system for shuffle expressions

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.

Threshold circuits for iterated matrix product and powering

Carlo Mereghetti, Beatrice Palano (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Threshold Circuits for Iterated Matrix Product and Powering

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 $k \times k$ matrices with integer or rational entries is studied. We call these two problems ${𝖨𝖬𝖯}_{𝗄}$ and ${𝖬𝖯𝖮𝖶}_{𝗄}$ , respectively, for short. We prove that: (i) For $k \geq 2$ , ${𝖨𝖬𝖯}_{𝗄}$ does not belong to ${TC}^{0}$ , unless ${TC}^{0} = {NC}^{1}$ .newline (ii) For stochastic matrices : ${𝖨𝖬𝖯}_{2}$ belongs to ${TC}^{0}$ while, for $k \geq 3$ , ${𝖨𝖬𝖯}_{𝗄}$ does not belong to ${TC}^{0}$ , unless ${TC}^{0} = {NC}^{1}$ . (iii) For any k, ${𝖬𝖯𝖮𝖶}_{𝗄}$ belongs to ${TC}^{0}$ .

Topological automata

Hartmut Ehrig, Wolfgang Kühnel (1974)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Topological deformation of higher dimensional automata.

Gaucher, Philippe, Goubault, Eric (2003)

Homology, Homotopy and Applications

Tours de Hanoï et automates

J.-P. Allouche, F. Dress (1990)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Towards an integrated theory of formal and natural languages

Petr Jirků (1975)

Kybernetika

Trace languages defined by regular string languages

Ijsbrand Jan Aalbersberg, Emo Welzl (1986)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Traces of term-automatic graphs

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...

Transcendental numbers having explicit $g$ -adic and Jacobi-Perron expansions

Jun-Ichi Tamura (1992)

Journal de théorie des nombres de Bordeaux

Transducteurs finis d'arbres et tests d'égalité

E. Lilin (1981)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Transductions algébriques

Michel Fliess (1970)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Transductions des langages de Chomsky

Maurice Nivat (1968)

Annales de l'institut Fourier

La feuille des applications dites $K$ -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 $C$ -langages) sur partie algébrique, partie rationnelle (ou $K$ -langage) sur partie rationnelle. On étudie sous le nom de langage compilable les parties algébriques qu’une $K$ -transduction univoque applique dans un ensemble de Dyck...

Transductions et familles de langages

Luc Boasson, Maurice Nivat (1971)

Mathématiques et Sciences Humaines

Transductions rationnelles décroissantes

Jeannine Leguy (1981)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Transformations of grammars and translation directed by $L R$ parsing

Bořivoj Melichar, Nguyen van Bac (2002)

Kybernetika

The class of $L R$ translation grammars is introduced. This class is characterized by a possibility to implement a formal translation as an algorithm directed by $L R$ parsing. To perform a translation, the conventional $L R$ parser is extended by a facility to perform output operations within the parsing actions shift and reduce. The definitions of Kernel $(R)$ - and $L R$ -translation grammars are presented. The transformations shaking-down and postponing that enable to transform some translation grammars into Kernel...

Transformations of translation grammars

Bořivoj Melichar (1994)

Kybernetika

Translation from classical two-way automata to pebble two-way automata

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,...

Currently displaying 41 – 60 of 75

Previous Page 3 Next