Search results for "Regular language"

Splicing Systems from Past to Future: Old and New Challenges

2014

A splicing system is a formal model of a recombinant behaviour of sets of double stranded DNA molecules when acted on by restriction enzymes and ligase. In this survey we will concentrate on a specific behaviour of a type of splicing systems, introduced by P\u{a}un and subsequently developed by many researchers in both linear and circular case of splicing definition. In particular, we will present recent results on this topic and how they stimulate new challenging investigations.

Ambiguity and complementation in recognizable two-dimensional languages

2008

The theory of one-dimensional (word) languages is well founded and investigated since fifties. From several years, the increasing interest for pattern recognition and image processing motivated the research on two-dimensional or picture languages, and nowadays this is a research field of great interest. A first attempt to formalize the concept of finite state recognizability for two-dimensional languages can be attributed to Blum and Hewitt ([7]) who started in 1967 the study of finite state devices that can define two-dimensional languages, with the aim to finding a counterpart of what regular languages are in one dimension. Since then, many approaches have been presented in the literature…

Cancellation, pumping and permutation in formal languages

1984

Extending formal language hierarchies to higher dimensions

1999

Languages associated with saturated formations of groups

2013

International audience; In a previous paper, the authors have shown that Eilenberg's variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower.; Dans un article précédent, les auteurs avaient montré comment étendre le théorème des variétés d'Eilenberg à des structures plus g…

Learning a class of regular expressions via restricted subset queries

1992

A wide class of regular expressions non-representable as unions of “smaller” expressions is shown to be polynomial-time learnable via restricted subset queries from arbitrary representative examples “reflecting” the loop structure and a way the input example is obtained from the unknown expression. The corresponding subclass of regular expressions of loop depth at most 1 is shown to be learnable from representative examples via membership queries. A wide class of expressions with loops A+ of arbitrary loop depth is shown to be learnable via restricted subset queries from arbitrary examples.

A challenging family of automata for classical minimization algorithms

2010

In this paper a particular family of deterministic automata that was built to reach the worst case complexity of Hopcroft's state minimization algorithm is considered. This family is also challenging for the two other classical minimization algorithms: it achieves the worst case for Moore's algorithm, as a consequence of a result by Berstel et al., and is of at least quadratic complexity for Brzozowski's solution, which is our main contribution. It therefore constitutes an interesting family, which can be useful to measure the efficiency of implementations of well-known or new minimization algorithms.

CODING PARTITIONS OF REGULAR SETS

2009

A coding partition of a set of words partitions this set into classes such that whenever a sequence, of minimal length, has two distinct factorizations, the words of these factorizations belong to the same class. The canonical coding partition is the finest coding partition that partitions the set of words in at most one unambiguous class and other classes that localize the ambiguities in the factorizations of finite sequences. We prove that the canonical coding partition of a regular set contains a finite number of regular classes and we give an algorithm for computing this partition. From this we derive a canonical decomposition of a regular monoid into a free product of finitely many re…

The Many Faces of a Translation

2000

First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts to "V-translations" and "V-single-valued-NFTs", where V is an arbitrary monoid pseudovariety. More strikingly, 2-way V-machines are introduced, and the following three models are shown exactly equivalent to Eilenberg's classical notion of a bimachine when V is a group variety or when V is the variety of aperiodic monoids: V-translations, V-single-valued-NFTs and 2-way V-transducers.

Patterns in words and languages

2004

AbstractA word p, over the alphabet of variables E, is a pattern of a word w over A if there exists a non-erasing morphism h from E∗ to A∗ such that h(p)=w. If we take E=A, given two words u,v∈A∗, we write u⩽v if u is a pattern of v. The restriction of ⩽ to aA∗, where A is the binary alphabet {a,b}, is a partial order relation. We introduce, given a word v, the set P(v) of all words u such that u⩽v. P(v), with the relation ⩽, is a poset and it is called the pattern poset of v. The first part of the paper is devoted to investigate the relationships between the structure of the poset P(v) and the combinatorial properties of the word v. In the last section, for a given language L, we consider …