EUDML | Efficient weighted expressions conversion

Skip to main content (access key 's'), Skip to navigation (access key 'n'), Accessibility information (access key '0')

Displaying similar documents to “Efficient weighted expressions conversion”

The theory of regular events. II

Havel, Ivan M. (1969)

Kybernetika

Similarity:

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

Computing $ε$ -free NFA from regular expressions in $O (n {log}^{2} (n))$ time

Christian Hagenah, Anca Muscholl (2000)

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

Similarity:

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 $\cup_{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...

Computing the Rabin index of a parity automaton

Olivier Carton, Ramón Maceiras (1999)

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

Similarity:

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.

Prolog infinite trees and automata

Solange Coupet-Grimal (1991)

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

Similarity:

Translation from classical two-way automata to pebble two-way automata

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

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

Similarity:

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some $ℓ$ additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with $ℓ$ nested pebbles....