Subtree Matching by Pushdown Automata
Suites algébriques, automates et substitutions
Summaries of articles published in this issue
Superiority of one-way and realtime quantum machines∗∗∗
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic...
Superiority of one-way and realtime quantum machines
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model...
Superiority of one-way and realtime quantum machines∗∗∗
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic...
Supervisory controller design for timed-place Petri nets
Supervisory controller design to avoid deadlock in discrete-event systems modeled by timed-place Petri nets (TPPNs) is considered. The recently introduced approach of place-stretching is utilized for this purpose. In this approach, given an original TPPN (OPN), a new TPPN, called the place-stretched Petri net (PSPN), is obtained. The PSPN has the property that its marking vector is sufficient to represent its state. By using this property, a supervisory controller design approach for TPPNs to avoid...
Supporting CAE parallel computations with IE-graph solid representation.
Sur des notions algébriques liées à l'analyse syntaxique
Sur des points fixes de morphismes d'un monoïde libre
Sur la classification syntaxique.
Sur la complexité de mots infinis engendrés par des -automates dénombrables
On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de -automates déterministes dénombrables de degré borné, ou de manière équivalente, engendrés par des substitutions de longueur constante uniformément bornées sur un alphabet dénombrable. En particulier, on montre que la complexité de tels mots est au plus polynomiale et que, sur plusieurs exemples, elle est au plus de l’ordre de grandeur de .
Sur la complexité du principe de Tarski-Seidenberg
Sur la complexité du principe de Tarski-Seidenberg
Sur la complexité d'un problème de codage
Sur la structure des automates probabilistes
Sur l'auto-stabilisation dans un réseau d'ordinateurs
Sur le noyau d'un homomorphisme du monoïde libre dans un groupe libre
Sur le produit avec compteur modulo un nombre premier
Sur les automates qui reconnaissent une famille de langages.