Efficient weighted expressions conversion

Faissal Ouardi; Djelloul Ziadi

Displaying similar documents to “Efficient weighted expressions conversion”

Computing -Free NFA from Regular Expressions in ( log()) Time

Christian Hagenah, Anca Muscholl (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The standard procedure to transform a regular expression of size to an -free nondeterministic finite automaton yields automata with states and ( ) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic showed how to build an -free NFA with only ( log()) transitions. The current lower bound on the number of transitions is Ω( log()). A rough running time estimation for the common follow sets (CFS) construction proposed...

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2011)

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

Similarity:

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton is hyper-minimized if no automaton with fewer states is almost equivalent to . A regular language is canonical if the minimal automaton accepting is hyper-minimized. The asymptotic state complexity () of a regular language is the number of states of a hyper-minimized automaton for a language finitely different from . In this paper we show...

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Regularity of languages defined by formal series with isolated cut point

Alberto Bertoni, Maria Paola Bianchi, Flavi D’Alessandro (2012)

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

Similarity:

Let = { ∈ | () } be the language recognized by a formal series : → ℝ with isolated cut point . We provide new conditions that guarantee the regularity of the language in the case that is rational or is a Hadamard quotient of rational series. Moreover the decidability property of such conditions is investigated.

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and...

On Conjugacy of Languages

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

RAIRO - Theoretical Informatics and Applications

Similarity:

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

Integers in number systems with positive and negative quadratic Pisot base

Z. Masáková, T. Vávra (2014)

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

Similarity:

We consider numeration systems with base and − , for quadratic Pisot numbers and focus on comparing the combinatorial structure of the sets Z and Z of numbers with integer expansion in base , resp. − . Our main result is the comparison of languages of infinite words and coding the ordering of distances between consecutive - and (− )-integers. It turns out that for a class of roots of − − , the languages coincide, while for other...

Computing the Rabin Index of a Parity Automaton

Olivier Carton, Ramón Maceiras (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The Rabin index of a rational language of infinite words given by a parity automaton with states is computable in time ( ) where is the cardinality of the alphabet. The number of values used by a parity acceptance condition is always greater than the Rabin index and conversely, the acceptance condition of a parity automaton can always be replaced by an equivalent acceptance condition whose number of used values is exactly the Rabin index. This...