Leftist grammars and the chomsky hierarchy

JURDZINSKI, Tomasz ; LORYS, Krzysztof

In: FCT 2005 : fundamentals of computationals theory (Lübeck, 17-20 August 2005)Lecture notes in computer science :293-304

Konferenz - print, 10 ref

Wie komme ich dran?

Leftist grammars can be characterized in terms of rules of the form a → ba and cd → d, without distinction between terminals and nonterminals. They were introduced by Motwani et. al. [9], where the accessibility problem for some general protection system was related to the membership problem of these grammars. This protection system was originally proposed in [3,10] in the context of Java virtual worlds. We show that the set of languages defined by general leftist grammars is not included in CFL, answering in negative a question from [9]. Moreover, we relate some restricted but naturally defined variants of leftist grammars to the language classes of the Chomsky hierarchy.

Titel:	Leftist grammars and the chomsky hierarchy
Autor/in / Beteiligte Person:	JURDZINSKI, Tomasz ; LORYS, Krzysztof
Link:	E-Journal im Bestand der UB Hagen? View record from PASCAL Archive
Quelle:	FCT 2005 : fundamentals of computationals theory (Lübeck, 17-20 August 2005)Lecture notes in computer science :293-304
Veröffentlichung:	Berlin: Springer, 2005
Medientyp:	Konferenz
Umfang:	print, 10 ref
ISSN:	0302-9743 (print)
Schlagwort:	Control theory, operational research Automatique, recherche opérationnelle Computer science Informatique Sciences exactes et technologie Exact sciences and technology Sciences appliquees Applied sciences Informatique; automatique theorique; systemes Computer science; control theory; systems Informatique théorique Theoretical computing Accessibilité Accessibility Accesibilidad Classe langage Language class Clase lenguaje Grammaire Chomsky Chomsky grammar Gramática Chomsky Computer theory Informática teórica Langage JAVA JAVA language Lenguaje JAVA Réalité virtuelle Virtual reality Realidad virtual Répondeur Responder Contestador Système protection Protection system Sistema protección Terminal
Sonstiges:	Nachgewiesen in: PASCAL Archive Sprachen: English Original Material: INIST-CNRS Document Type: Conference Paper File Description: text Language: English Author Affiliations: Institute of Computer Science, Wroclaw University, Przesmyckiego 20, 51151 Wroclaw, Poland Rights: Copyright 2005 INIST-CNRS ; CC BY 4.0 ; Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS Notes: Computer science; theoretical automation; systems

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.