Displaying similar documents to “Efficient weighted expressions conversion”

Conversion of regular expressions into realtime automata

Viliam Geffert, L'ubomíra Ištoňová (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider conversions of regular expressions into -realtime finite state automata, , automata in which the number of consecutive uses of -transitions, along any computation path, is bounded by a fixed constant . For -realtime automata, , for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only states, log) -transitions, and alphabet-transitions....

Efficiency of automata in semi-commutation verification techniques

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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 et al. [IEEE Comput. Soc. (2001) 399–408] proved that the class of regular languages L – called APC – of the form ∪ j L 0 , j L 1 , j L 2 , j ... L k j , j , where the union is finite and each L i , j is either a single symbol or a language of the form B * with B a subset of the alphabet, is...

Incremental DFA minimisation

Marco Almeida, Nelma Moreira, Rogério Reis (2014)

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

Similarity:

We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.