Brzozowski Janusz; Sinnamon Corwin: Complexity of right-ideal, prefix-closed, and prefix-free regular languages. In: Acta cybernetica, (23) 1. pp. 9-41. (2017)
Előnézet |
Cikk, tanulmány, mű
actacyb_23_1_2017_3.pdf Letöltés (362kB) | Előnézet |
Absztrakt (kivonat)
A language L over an alphabet Σ is prefix-convex if, for any words x, y, z ϵ Σ* , whenever x and xyz are in L, then so is xy. Prefix-convex languages include right-ideal, prefix-closed, and prefix-free languages as special cases. We examine complexity properties of these special prefix-convex languages. In particular, we study the quotient/state complexity of boolean operations, product (concatenation), star, and reversal, the size of the syntactic semigroup, and the quotient complexity of atoms. For binary operations we use arguments with different alphabets when appropriate; this leads to higher tight upper bounds than those obtained with equal alphabets. We exhibit right-ideal, prefix-closed, and prefix-free languages that meet the complexity bounds for all the measures listed above.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2017 |
| Kötet: | 23 |
| Szám: | 1 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 9-41 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/50021/ |
| DOI: | 10.14232/actacyb.23.1.2017.3 |
| Kulcsszavak: | Kibernetika - nyelvészet, Matematikai nyelvészet |
| Megjegyzések: | Bibliogr.: p. 39-41. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.01. Matematika 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2018. feb. 12. 08:27 |
| Utolsó módosítás: | 2022. jún. 20. 14:17 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/50061 |
 |
Tétel nézet |
