|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 6 van 7 gevonden artikelen
| Titel: |
Quadratic Algorithms for Testing of Codes and ◊-Codes |
| Auteur: |
Han, Nguyen Dinh Vinh, Ho Ngoc Thang, Dang Quyet Huy, Phan Trung |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 130 (2014) nr. 2 pagina's 163-177 |
| Jaar: |
2014-02-20 |
| Inhoud: |
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 \subseteq M$, X = ϕ−1(B), decides in time complexity $\mathcal{O}(n^2)$ 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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 6 van 7 gevonden artikelen
| << vorige | volgende >> |