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

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 UjL0,jL1,jL2,j...Lkj,j, where the union is finite and each Li,j is either a single symbol or a language of the form B* with B a subset of the alphabet, is closed under all semi-commutation relations R. Moreover a recursive...

We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the number...

We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the...

We present an on-line linear time and space algorithm to check if an integer array $f$ is the border array of at least one string $w$ built on a bounded or unbounded size alphabet $\Sigma$. First of all, we show a bijection between the border array of a string $w$ and the skeleton of the DFA recognizing ${\Sigma }^{*}w$, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a skeleton of SMA...

We present an on-line linear time and space algorithm to check if an integer array f is the border array of at least one string w built on a bounded or unbounded size alphabet Σ. First of all, we show a bijection between the border array of a string w and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a...

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

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(nlog2(n)) transitions. This method has been implemented efficiently in O(nlog2(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(nlog2(n)) time.

We consider shifted equality sets of the form $E_G(a,g_1,g_2)=\{w\mid g_1\left(w\right)=a{g}_2\left(w\right)\}$, where $g_1$ and $g_2$ are nonerasing morphisms and $a$ is a letter. We are interested in the family consisting of the languages $h\left(E_G\left(J\right)\right)$, where $h$ is a coding and $E_G\left(J\right)$ is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language $L\subseteq A^{*}$ is a projection of a shifted equality set, that is, $L={\pi }_A\left(E_G(a,g_1,g_2)\right)$ for some (nonerasing) morphisms $g_1$ and $g_2$ and a letter $a$, where ${\pi }_A$ deletes the letters not in $A$. Then we deduce...

We consider shifted equality sets of the form EG(a,g1,g2) = {ω | g1(ω) = ag2(ω)}, where g1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and (EG(J)) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L ⊆ A* is a projection of a shifted equality set, that is, L = πA(EG(a,g1,g2)) for some (nonerasing) morphisms g1...