Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26435
Titel: A representation theorem of infinite dimensional algebras and applications to language theory
Verfasser: Hotz, Günter
Sprache: Englisch
Erscheinungsjahr: 1983
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: We assign to each c.f. grammar G an infinite dimensionale algebra A_{R}(G) over a semiring R. From a representation \varphi of A_{R}(G) in R<Z^{(*)}<, when Z^{(*)} is a certain polycyclic monoid, we derive easily the theorems of Shamir-Nivat-Salomaa, Chomsky-Schützenberger, Greibach about a hardest c.f. languages and Greibach N.F. LL(k) und LR(k) languages get an easy algebraic characterisation, which generalises to non deterministic LL and LR-languages, which are linear in time and space too.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-51268
hdl:20.500.11880/26491
http://dx.doi.org/10.22028/D291-26435
Schriftenreihe: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Band: 1983/14
SciDok-Publikation: 2-Apr-2013
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1983_14.pdf42,17 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.