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 30 Next

Displaying 581 – 600 of 948

Showing per page

On Varieties of Literally Idempotent Languages

Ondřej Klíma, Libor Polák (2008)

RAIRO - Theoretical Informatics and Applications

A language L ⊆A* is literally idempotent in case that ua2v ∈ L if and only if uav ∈ L, for each u,v ∈ A*, a ∈ A. Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the...

On z -submonoids and z -codes

M. Madonia, S. Salemi, T. Sportelli (1991)

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

One-Rule Length-Preserving Rewrite Systems and Rational Transductions

Michel Latteux, Yves Roos (2014)

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

We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side u and the right-hand side v of the rule of the system are not quasi-conjugate or are equal, that means if u and v are distinct, there do not exist words x, y and z such that u = xyz and v = zyx. We...

On-line finite automata for addition in some numeration systems

Christiane Frougny (2010)

RAIRO - Theoretical Informatics and Applications

We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base β and addition in base βm is given. Results on addition in base β = b m , where b is a relative integer, follow. We also show that addition in base the golden ratio is computable by an on-line...

Parikh test sets for commutative languages

Štěpán Holub (2008)

RAIRO - Theoretical Informatics and Applications

A set T ⊆ L is a Parikh test set of L if c(T) is a test set of c(L). We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.

Permissive strategies : from parity games to safety games

Julien Bernet, David Janin, Igor Walukiewicz (2002)

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

It is proposed to compare strategies in a parity game by comparing the sets of behaviours they allow. For such a game, there may be no winning strategy that encompasses all the behaviours of all winning strategies. It is shown, however, that there always exists a permissive strategy that encompasses all the behaviours of all memoryless strategies. An algorithm for finding such a permissive strategy is presented. Its complexity matches currently known upper bounds for the simpler problem of finding...

Permissive strategies: from parity games to safety games

Julien Bernet, David Janin, Igor Walukiewicz (2010)

RAIRO - Theoretical Informatics and Applications

It is proposed to compare strategies in a parity game by comparing the sets of behaviours they allow. For such a game, there may be no winning strategy that encompasses all the behaviours of all winning strategies. It is shown, however, that there always exists a permissive strategy that encompasses all the behaviours of all memoryless strategies. An algorithm for finding such a permissive strategy is presented. Its complexity matches currently known upper bounds for the simpler problem...

Polynomial languages with finite antidictionaries

Arseny M. Shur (2009)

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

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

Currently displaying 581 – 600 of 948