The search session has expired. Please query the service again.

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.