On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata
| dc.date.accessioned | 2008-11-18T08:31:39Z | |
| dc.date.available | 2008-11-18T08:31:39Z | |
| dc.date.issued | 2008-11-18T08:31:39Z | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2008111825149 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2008111825149 | |
| dc.format.extent | 265090 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | analysis by reduction | eng |
| dc.subject | restarting automaton | eng |
| dc.subject | parallel communicating grammar system | eng |
| dc.subject | generation complexity | eng |
| dc.subject | distribution complexity | eng |
| dc.subject | characteristic analysis | eng |
| dc.subject.ddc | 004 | |
| dc.title | On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata | eng |
| dc.type | Technischer Report | |
| dcterms.abstract | This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Pardubská, Dana | |
| dcterms.creator | Plátek, Martin | |
| dcterms.creator | Otto, Friedrich | |
| dcterms.isPartOf | Kasseler Informatikschriften ;; 2008, 4 | ger |
| dc.subject.ccs | F.1.1 | |
| dc.subject.ccs | F.4.3 | |
| dcterms.source.series | Kasseler Informatikschriften | ger |
| dcterms.source.volume | 2008, 4 | ger |
