On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

Simple item page
dc.date.accessioned2008-11-18T08:31:39Z
dc.date.available2008-11-18T08:31:39Z
dc.date.issued2008-11-18T08:31:39Z
dc.format.extent265090 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.uriurn:nbn:de:hebis:34-2008111825149
dc.identifier.urihttp://hdl.handle.net/123456789/2008111825149
dc.language.isoeng
dc.rightsUrheberrechtlich geschützt
dc.rights.urihttps://rightsstatements.org/page/InC/1.0/
dc.subjectanalysis by reductioneng
dc.subjectrestarting automatoneng
dc.subjectparallel communicating grammar systemeng
dc.subjectgeneration complexityeng
dc.subjectdistribution complexityeng
dc.subjectcharacteristic analysiseng
dc.subject.ccsF.1.1
dc.subject.ccsF.4.3
dc.subject.ddc004
dc.titleOn Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automataeng
dc.typeTechnischer Report
dcterms.abstractThis 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.accessRightsopen access
dcterms.creatorPardubská, Dana
dcterms.creatorPlátek, Martin
dcterms.creatorOtto, Friedrich
dcterms.isPartOfKasseler Informatikschriften ;; 2008, 4ger
dcterms.source.seriesKasseler Informatikschriftenger
dcterms.source.volume2008, 4ger

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Technicalreport2008_4.pdf
Size:
221.14 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.33 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Kasseler Informatikschriften (KIS)