Search results for "monoid"
showing 10 items of 75 documents
On languages factorizing the free monoid
1996
A language X⊂A* is called factorizing if there exists a language Y⊂A* such that XY = A* This work was partially supported by ESPRIT-EBRA project ASMICS contact 6317 and project 40% MURST “Algoritmi, Modelli di Calcolo e Strutture Informative”. and the product is unambiguous. First we give a combinatorial characterization of factorizing languages. Further we prove that it is decidable whether a regular language X is factorizing and we construct an automaton recognizing the corresponding language Y. For finite languages we show that it suffices to consider words of bounded length. A complete characterization of factorizing languages with three words and explicit regular expression for the co…
Words and forbidden factors
2002
AbstractGiven a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word w we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two p…
Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups
1999
It is known that a number of algebraic properties of the braid groups extend to arbitrary finite Coxeter-type Artin groups. Here we show how to extend the results to more general groups that we call Garside groups. Define a Gaussian monoid to be a finitely generated cancellative monoid where the expressions of a given element have bounded lengths, and where left and right lowest common multiples exist. A Garside monoid is a Gaussian monoid in which the left and right lowest common multiples satisfy an additional symmetry condition. A Gaussian group is the group of fractions of a Gaussian monoid, and a Garside group is the group of fractions of a Garside monoid. Braid groups and, more genera…
Iterative pairs and multitape automata
1996
In this paper we prove that if every iterative k-tuple of a language L recognized by a k-tape automaton is very degenerate, then L is recognizable. Moreover, we prove that if L is an aperiodic langnage recognized by a deterministic k-tape automaton, then L is recognizable.
On the Shuffle of Star-Free Languages
2012
Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
2008
We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumaki on the cha- racterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators, we prove that if H and K are two finitely generated submonoids generated by prefix sets such that the product automaton associated to H ∩ K has a given special property then �(H ∩ K) ≤ �(H)�(K…
Quantum Finite Automata and Logics
2006
The connection between measure once quantum finite automata (MO-QFA) and logic is studied in this paper. The language class recognized by MO-QFA is compared to languages described by the first order logics and modular logics. And the equivalence between languages accepted by MO-QFA and languages described by formulas using Lindstrom quantifier is shown.
Periodicity vectors for labelled trees
2003
AbstractThe concept of a periodicity vector is introduced in the context of labelled trees, and some new periodicity theorems are obtained. These results constitute generalizations of the classical periodicity theorem of Fine and Wilf for words. The concept of a tree congruence is also generalized and the isomorphism between the lattice of tree congruences and the lattice of unlabelled trees (prefix codes) is established.
Faunal invasions as a source of morphological constraints and innovations? The diversification of the early Cardioceratidae (Ammonoidea; Middle Juras…
2005
Abstract Multivariate analysis of shell characters and quantification of morphological diversity (morphospace occupation and disparity) are used here to investigate the modes of morphological diversification of ammonites. We define five events in early cardioceratid history that connect geographical changes causing emigration or immigration phases with biodiversity dynamics: (1) the initial colonization of the Arctic Basin by the Cardioceratidae at the end of the Bajocian, Middle Jurassic; (2) the first appearance of the Kosmoceratidae clade in the Boreal Realm during the Bathonian; (3) the ensuing expansion phase of this clade in the Boreal Realm; (4) the first phase of migration of the Ca…
Ammonite Faunal Dynamics Across Bio-Events During the Mid-and Late Cretaceous Along the Russian Pacific Coast
2012
The present paper focuses on the evolutionary dynamics of ammonites from sections along the Russian Pacific coast during the mid-and Late Cretaceous. Changes in ammonite diversity (i.e., disappearance [extinction or emigration], appearance [origination or immigration], and total number of species present) constitute the basis for the identification of the main bio-events. The regional diversity curve reflects all global mass extinctions, faunal turnovers, and radiations. In the case of the Pacific coastal regions, such bio-events (which are comparatively easily recognised and have been described in detail), rather than first or last appearance datums of index species, should be used for glo…