Technischer Report
On Alternating Non-Context-Free Grammars
Abstract
We study several extensions of the notion of alternation from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. Thereby new grammatical characterizations are obtained for the class of languages that are accepted by alternating pushdown automata.
Sponsorship
Die Arbeit von Herrn Prof. Dr. Etsuro Moriya wurde durch einen Grant der Waseda University, Tokio, gefördert (Waseda University Grant for Special Research Projects #2006B-073).Citation
@techreport{urn:nbn:de:hebis:34-2007110719587,
author={Moriya, Etsuro and Otto, Friedrich},
title={On Alternating Non-Context-Free Grammars},
year={2007}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2007$n2007 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2007110719587 3000 Moriya, Etsuro 3010 Otto, Friedrich 4000 On Alternating Non-Context-Free Grammars / Moriya, Etsuro 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2007110719587=x R 4204 \$dTechnischer Report 4170 Kasseler Informatikschriften ;; 2007, 6 7136 ##0##urn:nbn:de:hebis:34-2007110719587
2007-11-07T12:22:02Z 2007-11-07T12:22:02Z 2007-11-07T12:22:02Z urn:nbn:de:hebis:34-2007110719587 http://hdl.handle.net/123456789/2007110719587 Die Arbeit von Herrn Prof. Dr. Etsuro Moriya wurde durch einen Grant der Waseda University, Tokio, gefördert (Waseda University Grant for Special Research Projects #2006B-073). 232627 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Grammar Alternation Alternating context-sensitive grammar Alternating phrase-structure grammar State-alternating grammar Leftmost derivation Language class Alternating pushdown automaton Alternating linear bounded automaton 004 On Alternating Non-Context-Free Grammars Technischer Report We study several extensions of the notion of alternation from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. Thereby new grammatical characterizations are obtained for the class of languages that are accepted by alternating pushdown automata. open access Moriya, Etsuro Otto, Friedrich Kasseler Informatikschriften ;; 2007, 6 Die Arbeit entstand zu wesentlichen Teilen während eines Aufenthaltes von Herrn Prof. Dr. Etsuro Moriya im September 2007 in Kassel. F.1.2 F.4.2 F.4.3 Kasseler Informatikschriften 2007, 6
The following license files are associated with this item:
:Urheberrechtlich geschützt
Related items
Showing items related by title, author, creator and subject.
-
Rezension[Rezension zu:] A Grammar of Signs: Bartolo da Sassoferrato's “Tract on Insignia and Coats of Arms." By Osvaldo Cavallar, Susanne Degenring, and Julius Kirshner. Studies in Comparative Legal History. Berkeley and Los Angeles: Robbins Collection Publications, 1995. Pp. 200. $25.00. Baumgärtner, Ingrid (1997)
-
Teil eines BuchesDependency Grammar and Valency Theory Ágel, Vilmos; Fischer, Klaus (Oxford University PressOxford, 2010)