Advertisement
Published in:
2012 | OriginalPaper | Chapter
A Quadratic Algorithm for Testing of Omega-Codes
Authors : Nguyen Dinh Han, Phan Trung Huy, Dang Quyet Thang
Published in: Intelligent Information and Database Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider a special class of codes, namely
ω
-codes related to infinite word which had been studied by many authors. Until now, the best algorithm to test whether a regular language
X
is an
ω
-code has time complexity
${\cal O}(n^3)$
, where
n
is the size of the transition monoid of the minimal automaton recognizing
X
. In this paper, with any monoid
M
saturating
X
(the transition monoid above is only a special case), we propose a new test and establish a quadratic testing algorithm with time complexity
${\cal O}(n^2)$
to verify if
X
is an
ω
-code, where
n
is Card(
M
).