On alternating phrase-structure grammars

Etsuro Moriya; Friedrich Otto

doi:10.1007/978-3-540-88282-4_36

On alternating phrase-structure grammars

Etsuro Moriya^*, Friedrich Otto

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

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.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	397-408
Number of pages	12
Volume	5196 LNCS
DOIs	https://doi.org/10.1007/978-3-540-88282-4_36
Publication status	Published - 2008
Event	2nd International Conference on Language and Automata Theory and Applications, LATA 2008 - Tarragona Duration: 2008 Mar 13 → 2008 Mar 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5196 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	2nd International Conference on Language and Automata Theory and Applications, LATA 2008
City	Tarragona
Period	08/3/13 → 08/3/19

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

Access to Document

10.1007/978-3-540-88282-4_36

Cite this

Moriya, E., & Otto, F. (2008). On alternating phrase-structure grammars. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 5196 LNCS, pp. 397-408). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5196 LNCS). https://doi.org/10.1007/978-3-540-88282-4_36

On alternating phrase-structure grammars. / Moriya, Etsuro; Otto, Friedrich.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 5196 LNCS 2008. p. 397-408 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5196 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Moriya, E & Otto, F 2008, On alternating phrase-structure grammars. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 5196 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5196 LNCS, pp. 397-408, 2nd International Conference on Language and Automata Theory and Applications, LATA 2008, Tarragona, 08/3/13. https://doi.org/10.1007/978-3-540-88282-4_36

Moriya E, Otto F. On alternating phrase-structure grammars. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 5196 LNCS. 2008. p. 397-408. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-88282-4_36

Moriya, Etsuro ; Otto, Friedrich. / On alternating phrase-structure grammars. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 5196 LNCS 2008. pp. 397-408 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b9d8c1c284c84967ac7ac73475748999,

title = "On alternating phrase-structure 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.",

author = "Etsuro Moriya and Friedrich Otto",

year = "2008",

doi = "10.1007/978-3-540-88282-4_36",

language = "English",

isbn = "3540882812",

volume = "5196 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "397--408",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "2nd International Conference on Language and Automata Theory and Applications, LATA 2008 ; Conference date: 13-03-2008 Through 19-03-2008",

}

TY - GEN

T1 - On alternating phrase-structure grammars

AU - Moriya, Etsuro

AU - Otto, Friedrich

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

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

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

U2 - 10.1007/978-3-540-88282-4_36

DO - 10.1007/978-3-540-88282-4_36

M3 - Conference contribution

AN - SCOPUS:56449130944

SN - 3540882812

SN - 9783540882817

VL - 5196 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 397

EP - 408

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 2nd International Conference on Language and Automata Theory and Applications, LATA 2008

Y2 - 13 March 2008 through 19 March 2008

ER -

On alternating phrase-structure grammars

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this