Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.25673/42547| Titel: | Operational complexity and right linear grammars |
| Autor(en): | Dassow, Jürgen |
| Erscheinungsdatum: | 2021 |
| Art: | Artikel |
| Sprache: | Englisch |
| URN: | urn:nbn:de:gbv:ma9:1-1981185920-445019 |
| Schlagwörter: | Complexity of languages Linear grammars |
| Zusammenfassung: | For a regular language L, let Var(L) be the minimal number of nonterminals necessary to generate L by right linear grammars. Moreover, for natural numbers k1,k2,…,kn and an n-ary regularity preserving operation f, let gVarf(k1,k2,…,kn) be the set of all numbers k such that there are regular languages L1,L2,…,Ln such that Var(Li)=ki for 1≤i≤n and Var(f(L1,L2,…,Ln))=k. We completely determine the sets gVarf for the operations reversal, Kleene-closures + and ∗, and union; and we give partial results for product and intersection. |
| URI: | https://opendata.uni-halle.de//handle/1981185920/44501 http://dx.doi.org/10.25673/42547 |
| Open-Access: |  Open-Access-Publikation |
| Nutzungslizenz: |  (CC BY 4.0) Creative Commons Namensnennung 4.0 International |
| Sponsor/Geldgeber: | Projekt DEAL 2020 |
| Journal Titel: | Acta informatica |
| Verlag: | Springer |
| Verlagsort: | Berlin |
| Band: | 58 |
| Heft: | 2021 |
| Originalveröffentlichung: | 10.1007/s00236-020-00386-3 |
| Seitenanfang: | 281 |
| Seitenende: | 299 |
| Enthalten in den Sammlungen: | Fakultät für Informatik (OA) |
Dateien zu dieser Ressource:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| Dassow_Juergen_Operational_2021.pdf | Zweitveröffentlichung | 295.54 kB | Adobe PDF |  Öffnen/Anzeigen |