The theory of regular events. II

Havel, Ivan M.

Displaying similar documents to “The theory of regular events. II”

Some closure properties of the nondeterministic regular translations.

Pevac, Irena (1981)

Publications de l'Institut Mathématique. Nouvelle Série

Similarity:

The theory of regular events. I

Havel, Ivan M. (1969)

Kybernetika

Similarity:

On State Reduction In Deterministic Finite Transducers And Some Properties Of Deterministic Regular Translations

Irena Pevac (1982)

Publications de l'Institut Mathématique

Similarity:

Analysis of finite state automata by state isolation

Š. Ušćumlić, D. Bratičević (1978)

Matematički Vesnik

Similarity:

Closedness properties and decision problems for finite multi-tape automata

Peter H. Starke (1976)

Kybernetika

Similarity:

Extending regular expressions with homomorphic replacement

Henning Bordihn, Jürgen Dassow, Markus Holzer (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns,...

Efficient weighted expressions conversion

Faissal Ouardi, Djelloul Ziadi (2008)

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

Similarity:

J. Hromkovic et al. have given an elegant method to convert a regular expression of size $n$ into an $ε$ -free nondeterministic finite automaton having $O (n)$ states and $O (n {log}^{2} (n))$ transitions. This method has been implemented efficiently in $O (n {log}^{2} (n))$ 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 $O (n {log}^{2} (n))$ time.