Please use this identifier to cite or link to this item: doi:10.22028/D291-26435
Title: A representation theorem of infinite dimensional algebras and applications to language theory
Author(s): Hotz, Günter
Language: English
Year of Publication: 1983
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: 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 to this record: urn:nbn:de:bsz:291-scidok-51268
Series name: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Series volume: 1983/14
Date of registration: 2-Apr-2013
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1983_14.pdf42,17 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.