Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: submonoid

Sortuj według:

Ogranicz wyniki do:

On the Completion of Codes in Submonoids with Finite Rank

Néraud J.

Fundamenta Informaticae

2006

Vol. 74, nr 4

549-562

Let M be a submonoid of the free monoid A*, and let X Ě M be a variable length code (for short a code). X is weakly M-complete if and only if any word in M is a factor of some word in X* (cf [20]). In this paper, which is the full version of a result presented in [17], we are interested by an effective computation of a weakly M-complete code containing X, namely [^X] Ě M. In this framework, we consider the class of submonoids M of A* which have finite rank. We define the rank of M as the rank of the minimal automaton with behavior M, i.e. the smallest positive integer r such that a word w satisfies |Q.w| = r, where Q stands for the set of states (the action of the word w may be not defined on some state in Q). Regular submonoids are the most typical example of submonoids with finite rank. Given a submonoid with finite rank M Ě A*, and given a code X Ě M, we present a method of completion which makes only use of regular or boolean operations on sets. As a consequence, if M and X are regular sets then so is [^X].

Prelanguages versus submonoids

Ostravsky J.

Fundamenta Informaticae

2001

Vol. 46, nr 4

343-348

In [9] submonoids of a commutative monoid are characterized by means of their relations of domination, subgroups of a commutative monoid are characterized by means of their relations of double domination. The main purpose of this paper is to transfer these results to general monoids. The important means will be certain relations, which we shall study in detail.

Pregrammars versus submonoids

Ostravsky J.

Fundamenta Informaticae

1998

Vol. 36, nr 4

337-343

Prelanguages and pregrammars introduced present a generalization of languages and pure grammars. Relation of domination and double domination may be easily transferred from languages to prelanguages. In the present paper submonoids of a commutative monoid are characterized by means of their relations of domination: subgroups of a commutative group are characterized by means of their relations of double domination. The submonoid generated by a subset of a commutative monoid is constructed using a suitable pregrammar.