2012 | OriginalPaper | Buchkapitel
A Quadratic Algorithm for Testing of Omega-Codes
verfasst von : Nguyen Dinh Han, Phan Trung Huy, Dang Quyet Thang
Erschienen in: Intelligent Information and Database Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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
).