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

Displaying 101 – 120 of 186

Showing per page

On biautomata∗

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

RAIRO - Theoretical Informatics and Applications

We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language L its canonical biautomaton. This structure plays, among all biautomata recognizing the language L, the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language L. We expect that from the graph structure of this automaton one could decide the membership of a given language for certain...

On conjugacy of languages

Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2001)

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

We say that two languages X and Y are conjugates if they satisfy the conjugacy equation X Z = Z Y for some language Z . We study several problems associated with this equation. For example, we characterize all sets which are conjugated v i a a two-element biprefix set Z , as well as all two-element sets which are conjugates.

On Conjugacy of Languages

Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2010)

RAIRO - Theoretical Informatics and Applications

We say that two languages X and Y are conjugates if they satisfy the conjugacy equationXZ = ZY for some language Z. We study several problems associated with this equation. For example, we characterize all sets which are conjugated via a two-element biprefix set Z, as well as all two-element sets which are conjugates.

On graph products of automatic monoids

A. Veloso Da Costa (2001)

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

The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.

On graph products of automatic monoids

A. Veloso da Costa (2010)

RAIRO - Theoretical Informatics and Applications

The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.

On shuffle ideals

Pierre-Cyrille Héam (2002)

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

A shuffle ideal is a language which is a finite union of languages of the form A * a 1 A * ⋯ A * a k A * where A is a finite alphabet and the a i ’s are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally...

On Shuffle Ideals

Pierre-Cyrille Héam (2010)

RAIRO - Theoretical Informatics and Applications


A shuffle ideal is a language which is a finite union of languages of the form A*a1A*...A*ak where A is a finite alphabet and the ai's are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for...

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2004)

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

This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2010)

RAIRO - Theoretical Informatics and Applications

This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...

On the growth rates of complexity of threshold languages

Arseny M. Shur, Irina A. Gorbunova (2010)

RAIRO - Theoretical Informatics and Applications

Threshold languages, which are the (k/(k–1))+-free languages over k-letter alphabets with k ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant α ^ ≈ 1 . 242 as k tends to infinity.

On the simplest centralizer of a language

Paolo Massazza, Petri Salmela (2006)

RAIRO - Theoretical Informatics and Applications

Given a finite alphabet Σ and a language L ⊆ ∑+, the centralizer of L is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of L (with respect to a lexicographic order) is prefix distinguishable in L then the centralizer of L is as simple as possible, that is, the submonoid L*. This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.

Currently displaying 101 – 120 of 186