|
| << 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 5 van 7 gevonden artikelen
| Titel: |
Outfix-Free Regular Languages and Prime Outfix-Free Decomposition |
| Auteur: |
Han, Yo-Sub Wood, Derick |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 81 (2008) nr. 4 pagina's 441-457 |
| Jaar: |
2008-01-07 |
| Inhoud: |
A string x is an outfix of a string y if there is a string w such that x_1wx_2 = y and x = x_1x_2. A set X of strings is outfix-free if no string in X is an outfix of any other string in X. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines outfix-freeness of regular languages. Note that outfix-free regular languages are always finite. We consider two cases: 1) a language is given as a finite set of strings and 2) a language is given by a finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfixfree regular languages and design a linear-time algorithm that computes prime outfix-free decomposition for outfix-free regular languages. We also demonstrate the uniqueness of prime outfix-free decomposition. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 5 van 7 gevonden artikelen
| << vorige | volgende >> |