Displaying similar documents to “Undecidability of the equivalence of finite substitutions on regular language”

Efficiency of automata in semi-commutation verification techniques

Gérard Cécé, Pierre-Cyrille Héam, Yann Mainier (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

Computing the image of a regular language by the transitive closure of a relation is a central question in regular model checking. In a recent paper Bouajjani [ (2001) 399–408] proved that the class of regular languages – called APC – of the form U ..., where the union is finite and each is either a single symbol or a language of the form with a subset of the alphabet, is closed under all semi-commutation relations . Moreover...

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...

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:

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...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

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

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...

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.

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...

Efficient weighted expressions conversion

Faissal Ouardi, Djelloul Ziadi (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

J. Hromkovic . have given an elegant method to convert a regular expression of size into an -free nondeterministic finite automaton having states and log ) transitions. This method has been implemented efficiently in log ) time by C. Hagenah and A. Muscholl. In this paper we extend this method to weighted regular expressions and we show that it can be achieved in log ) time.

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.