Some remarks on the stability problem for linear space automata and semicontinuity of cut point languages
Some results on finite maximal codes
Some results on the dot-depth hierarchy.
Some theorems on labelled bracketings used in transformational grammars
Space classes, intersection of languages and bounded erasing homomorphisms
Spezielle Gleichungen in freien Halbgruppen und eine Anwendung auf Normalformen regulärer Ereignisse
Square-free and overlap-free words
Squares and overlaps in the Thue-Morse sequence and some variants
We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are 2-regular. We also prove that changing any finite but nonzero number of bits in the Thue-Morse sequence creates an overlap, and any linear subsequence of the Thue-Morse sequence (except those corresponding to decimation by a power of 2) contains an overlap.
Stackautomaten in Labyrinthen.
State complexity of cyclic shift
The cyclic shift of a language , defined as =, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! 2, which shows that the state complexity...
State complexity of cyclic shift
The cyclic shift of a language L, defined as SHIFT(L) = {vu | uv ∈ L}, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov's pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl.11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! . 2(n-1)(n-2), which...
Strategies to scan pictures with automata based on Wang tiles
Wang automata are devices for picture language recognition recently introduced by us, which characterize the class REC of recognizable picture languages. Thus, Wang automata are equivalent to tiling systems or online tessellation acceptors, and are based like Wang systems on labeled Wang tiles. The present work focus on scanning strategies, to prove that the ones Wang automata are based on are those following four kinds of movements: boustrophedonic, “L-like”, “U-like”, and spirals.
Strategies to scan pictures with automata based on Wang tiles
Wang automata are devices for picture language recognition recently introduced by us, which characterize the class REC of recognizable picture languages. Thus, Wang automata are equivalent to tiling systems or online tessellation acceptors, and are based like Wang systems on labeled Wang tiles. The present work focus on scanning strategies, to prove that the ones Wang automata are based on are those following four kinds of movements: boustrophedonic, “L-like”, “U-like”, and spirals.
String distances and intrusion detection: Bridging the gap between formal languages and computer security
In this paper we analyze some intrusion detection strategies proposed in the literature and we show that they represent the various facets of a well known formal languages problem: computing the distance between a string x and a language L. In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language L and to the notion of distance adopted. As a further contribution we will also show that from...
Strong iterative pairs and the regularity of context-free languages
Strongly locally testable semigroups with commuting idempotents and related languages
Strongly locally testable semigroups with commuting idempotents and related languages
If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. S is strongly locally testable if whenever two words over the alphabet S have the same factors of a fixed length k, then the products of the letters of these words are equal. We had previously proved [19] that the syntactic semigroup of a rational language L is strongly locally testable if and only if L is both locally...
Structural unambiguity of formal languages
Structure de l'automate plein, réduit et inversible
Study of irreducible balanced pairs for substitutive languages
Let be a language. A balanced pair (u,v) consists of two words u and v in which have the same number of occurrences of each letter. It is irreducible if the pairs of strict prefixes of u and v of the same length do not form balanced pairs. In this article, we are interested in computing the set of irreducible balanced pairs on several cases of languages. We make connections with the balanced pairs algorithm and discrete geometrical constructions related to substitutive languages. We characterize...