A grammatical characterization of alternating pushdown automata

Etsuro Moriya

doi:10.1016/0304-3975(89)90023-6

A grammatical characterization of alternating pushdown automata

Etsuro Moriya^*

^*Corresponding author for this work

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

15 Citations (Scopus)

Abstract

The notion of an alternating context-free grammar is introduced and it is shown that the class of alternating context-free languages is equal to the class of languages accepted by alternating pushdown automata. Some properties on alternating context-free languages are also studied.

Original language	English
Pages (from-to)	75-85
Number of pages	11
Journal	Theoretical Computer Science
Volume	67
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(89)90023-6
Publication status	Published - 1989 Sept 5
Externally published	Yes

ASJC Scopus subject areas

Computational Theory and Mathematics

Access to Document

10.1016/0304-3975(89)90023-6

Cite this

@article{3227098c85224eacb13dfb1c4143636d,

title = "A grammatical characterization of alternating pushdown automata",

abstract = "The notion of an alternating context-free grammar is introduced and it is shown that the class of alternating context-free languages is equal to the class of languages accepted by alternating pushdown automata. Some properties on alternating context-free languages are also studied.",

author = "Etsuro Moriya",

year = "1989",

month = sep,

day = "5",

doi = "10.1016/0304-3975(89)90023-6",

language = "English",

volume = "67",

pages = "75--85",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - A grammatical characterization of alternating pushdown automata

AU - Moriya, Etsuro

PY - 1989/9/5

Y1 - 1989/9/5

N2 - The notion of an alternating context-free grammar is introduced and it is shown that the class of alternating context-free languages is equal to the class of languages accepted by alternating pushdown automata. Some properties on alternating context-free languages are also studied.

AB - The notion of an alternating context-free grammar is introduced and it is shown that the class of alternating context-free languages is equal to the class of languages accepted by alternating pushdown automata. Some properties on alternating context-free languages are also studied.

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

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

U2 - 10.1016/0304-3975(89)90023-6

DO - 10.1016/0304-3975(89)90023-6

M3 - Article

AN - SCOPUS:0024962437

SN - 0304-3975

VL - 67

SP - 75

EP - 85

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

A grammatical characterization of alternating pushdown automata

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this