Technischer Report
On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata
Zusammenfassung
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.
Zitieren
@techreport{urn:nbn:de:hebis:34-2008111825149,
author={Pardubská, Dana and Plátek, Martin and Otto, Friedrich},
title={On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata},
year={2008}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2008$n2008 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2008111825149 3000 Pardubská, Dana 3010 Plátek, Martin 3010 Otto, Friedrich 4000 On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata / Pardubská, Dana 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2008111825149=x R 4204 \$dTechnischer Report 4170 Kasseler Informatikschriften ;; 2008, 4 7136 ##0##urn:nbn:de:hebis:34-2008111825149
2008-11-18T08:31:39Z 2008-11-18T08:31:39Z 2008-11-18T08:31:39Z urn:nbn:de:hebis:34-2008111825149 http://hdl.handle.net/123456789/2008111825149 265090 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ analysis by reduction restarting automaton parallel communicating grammar system generation complexity distribution complexity characteristic analysis 004 On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata Technischer Report 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. open access Pardubská, Dana Plátek, Martin Otto, Friedrich Kasseler Informatikschriften ;; 2008, 4 F.1.1 F.4.3 Kasseler Informatikschriften 2008, 4
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden:
:Urheberrechtlich geschützt