Please use this identifier to cite or link to this item:
http://dx.doi.org/10.25673/42547Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Dassow, Jürgen | - |
| dc.date.accessioned | 2021-12-15T09:27:15Z | - |
| dc.date.available | 2021-12-15T09:27:15Z | - |
| dc.date.issued | 2021 | - |
| dc.date.submitted | 2021 | - |
| dc.identifier.uri | https://opendata.uni-halle.de//handle/1981185920/44501 | - |
| dc.identifier.uri | http://dx.doi.org/10.25673/42547 | - |
| dc.description.abstract | 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. | eng |
| dc.description.sponsorship | Projekt DEAL 2020 | - |
| dc.language.iso | eng | - |
| dc.relation.ispartof | http://link.springer.com/journal/236 | - |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | - |
| dc.subject | Complexity of languages | eng |
| dc.subject | Linear grammars | eng |
| dc.subject.ddc | 000 | - |
| dc.title | Operational complexity and right linear grammars | eng |
| dc.type | Article | - |
| dc.identifier.urn | urn:nbn:de:gbv:ma9:1-1981185920-445019 | - |
| local.versionType | publishedVersion | - |
| local.bibliographicCitation.journaltitle | Acta informatica | - |
| local.bibliographicCitation.volume | 58 | - |
| local.bibliographicCitation.issue | 2021 | - |
| local.bibliographicCitation.pagestart | 281 | - |
| local.bibliographicCitation.pageend | 299 | - |
| local.bibliographicCitation.publishername | Springer | - |
| local.bibliographicCitation.publisherplace | Berlin | - |
| local.bibliographicCitation.doi | 10.1007/s00236-020-00386-3 | - |
| local.openaccess | true | - |
| dc.identifier.ppn | 1782087230 | - |
| local.bibliographicCitation.year | 2021 | - |
| cbs.sru.importDate | 2021-12-15T09:21:37Z | - |
| local.bibliographicCitation | Enthalten in Acta informatica - Berlin : Springer, 1971 | - |
| local.accessrights.dnb | free | - |
| Appears in Collections: | Fakultät für Informatik (OA) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Dassow_Juergen_Operational_2021.pdf | Zweitveröffentlichung | 295.54 kB | Adobe PDF |  View/Open |