On alternating phrase-structure grammars

Etsuro Moriya; Friedrich Otto

doi:10.1142/S0129054110007106

On alternating phrase-structure grammars

Etsuro Moriya^*, Friedrich Otto

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.

Original language	English
Pages (from-to)	1-25
Number of pages	25
Journal	International Journal of Foundations of Computer Science
Volume	21
Issue number	1
DOIs	https://doi.org/10.1142/S0129054110007106
Publication status	Published - 2010 Feb

ASJC Scopus subject areas

Computer Science (miscellaneous)

Access to Document

10.1142/S0129054110007106

Cite this

@article{b324562351d34927aaf5def1068837e3,

title = "On alternating phrase-structure grammars",

abstract = "The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.",

author = "Etsuro Moriya and Friedrich Otto",

year = "2010",

month = feb,

doi = "10.1142/S0129054110007106",

language = "English",

volume = "21",

pages = "1--25",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "1",

}

TY - JOUR

T1 - On alternating phrase-structure grammars

AU - Moriya, Etsuro

AU - Otto, Friedrich

PY - 2010/2

Y1 - 2010/2

N2 - The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.

AB - The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.

UR - http://www.scopus.com/inward/record.url?scp=77951672727&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951672727&partnerID=8YFLogxK

U2 - 10.1142/S0129054110007106

DO - 10.1142/S0129054110007106

M3 - Article

AN - SCOPUS:77951672727

SN - 0129-0541

VL - 21

SP - 1

EP - 25

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 1

ER -

On alternating phrase-structure grammars

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this