Displaying 681 – 700 of 948

Showing per page

Sequential monotonicity for restarting automata

Tomasz Jurdziński, Friedrich Otto (2007)

RAIRO - Theoretical Informatics and Applications

As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only...

Séries formelles

Michel Fliess (1971)

Mathématiques et Sciences Humaines

La classification chomskienne des langages formels conduit à l'étude d'objets mathématiques nouveaux: les séries rationnelles et algébriques en variables non commutatives.

Series which are both max-plus and min-plus rational are unambiguous

Sylvain Lombardy, Jean Mairesse (2006)

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

Consider partial maps Σ * with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure...

Series which are both max-plus and min-plus rational are unambiguous

Sylvain Lombardy, Jean Mairesse (2010)

RAIRO - Theoretical Informatics and Applications

Consider partial maps ∑* → with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one that recognize the same series.

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2005)

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

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2010)

RAIRO - Theoretical Informatics and Applications

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...

Single-tape reset machines

S. A. Greibach, C. Wrathall (1986)

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

Some Algebraic Properties of Machine Poset of Infinite Words

Aleksandrs Belovs (2008)

RAIRO - Theoretical Informatics and Applications

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

Currently displaying 681 – 700 of 948