Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2014

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: quadratic algorithm

Sortuj według:

Ogranicz wyniki do:

Quadratic Algorithms for Testing of Codes and ◊-Codes

Han N. D., Vinh H. N., Thang D. Q., Huy P. T.

Fundamenta Informaticae

2014

Vol. 130, nr 2

163--177

The Sardinas-Patterson's test for codes has contributed many effective testing algorithms to the development of theory of codes, formal languages, etc. However, we will show that a modification of this test proposed in this paper can deduce more effective testing algorithms for codes. As a consequence, we establish a quadratic algorithm that, given as input a regular language X defined by a tuple (ϕ, M, B), where ϕ : A* → M is a monoid morphism saturating X, M is a finite monoid, B Í M, X = ϕ−1(B), decides in time complexity O(n2) whether X is a code, where n = Card(M). Specially, n can be chosen as the finite index of X. A quadratic algorithm for testing of ◊-codes is also established.