Chomsky-Schützenberger-type characterization of multiple context-free languages

Ryo Yoshinaka; Yuichi Kaji; Hiroyuki Seki

doi:10.1007/978-3-642-13089-2_50

Chomsky-Schützenberger-type characterization of multiple context-free languages

Ryo Yoshinaka, Yuichi Kaji, Hiroyuki Seki

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

9 Citations (Scopus)

Abstract

It is a well-known theorem by Chomsky and Schützenberger (1963) that every context-free language can be represented as a homomorphic image of the intersection of a Dyck language and a regular language. This paper gives a Chomsky-Schützenberger-type characterization for multiple context-free languages, which are a natural extension of context-free languages, with introducing the notion of multiple Dyck languages, which are also a generalization of Dyck languages.

Original language	English
Title of host publication	Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings
Pages	596-607
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-13089-2_50
Publication status	Published - 2010
Externally published	Yes
Event	4th International Conference on Language and Automata Theory and Applications, LATA 2010 - Trier, Germany Duration: 2010 May 24 → 2010 May 28

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6031 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	4th International Conference on Language and Automata Theory and Applications, LATA 2010
Country/Territory	Germany
City	Trier
Period	10/5/24 → 10/5/28

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-13089-2_50

Cite this

Yoshinaka, R., Kaji, Y., & Seki, H. (2010). Chomsky-Schützenberger-type characterization of multiple context-free languages. In Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings (pp. 596-607). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6031 LNCS). https://doi.org/10.1007/978-3-642-13089-2_50

Chomsky-Schützenberger-type characterization of multiple context-free languages. / Yoshinaka, Ryo; Kaji, Yuichi; Seki, Hiroyuki.
Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings. 2010. p. 596-607 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6031 LNCS).

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

Yoshinaka, R, Kaji, Y & Seki, H 2010, Chomsky-Schützenberger-type characterization of multiple context-free languages. in Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6031 LNCS, pp. 596-607, 4th International Conference on Language and Automata Theory and Applications, LATA 2010, Trier, Germany, 10/5/24. https://doi.org/10.1007/978-3-642-13089-2_50

Yoshinaka R, Kaji Y, Seki H. Chomsky-Schützenberger-type characterization of multiple context-free languages. In Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings. 2010. p. 596-607. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-13089-2_50

Yoshinaka, Ryo ; Kaji, Yuichi ; Seki, Hiroyuki. / Chomsky-Schützenberger-type characterization of multiple context-free languages. Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings. 2010. pp. 596-607 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7b5f3660e8de437480f194936b5eb713,

title = "Chomsky-Sch{\"u}tzenberger-type characterization of multiple context-free languages",

abstract = "It is a well-known theorem by Chomsky and Sch{\"u}tzenberger (1963) that every context-free language can be represented as a homomorphic image of the intersection of a Dyck language and a regular language. This paper gives a Chomsky-Sch{\"u}tzenberger-type characterization for multiple context-free languages, which are a natural extension of context-free languages, with introducing the notion of multiple Dyck languages, which are also a generalization of Dyck languages.",

author = "Ryo Yoshinaka and Yuichi Kaji and Hiroyuki Seki",

year = "2010",

doi = "10.1007/978-3-642-13089-2_50",

language = "English",

isbn = "3642130887",

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

pages = "596--607",

booktitle = "Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings",

note = "4th International Conference on Language and Automata Theory and Applications, LATA 2010 ; Conference date: 24-05-2010 Through 28-05-2010",

}

TY - GEN

T1 - Chomsky-Schützenberger-type characterization of multiple context-free languages

AU - Yoshinaka, Ryo

AU - Kaji, Yuichi

AU - Seki, Hiroyuki

PY - 2010

Y1 - 2010

N2 - It is a well-known theorem by Chomsky and Schützenberger (1963) that every context-free language can be represented as a homomorphic image of the intersection of a Dyck language and a regular language. This paper gives a Chomsky-Schützenberger-type characterization for multiple context-free languages, which are a natural extension of context-free languages, with introducing the notion of multiple Dyck languages, which are also a generalization of Dyck languages.

AB - It is a well-known theorem by Chomsky and Schützenberger (1963) that every context-free language can be represented as a homomorphic image of the intersection of a Dyck language and a regular language. This paper gives a Chomsky-Schützenberger-type characterization for multiple context-free languages, which are a natural extension of context-free languages, with introducing the notion of multiple Dyck languages, which are also a generalization of Dyck languages.

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

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

U2 - 10.1007/978-3-642-13089-2_50

DO - 10.1007/978-3-642-13089-2_50

M3 - Conference contribution

AN - SCOPUS:77953802466

SN - 3642130887

SN - 9783642130885

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

SP - 596

EP - 607

BT - Language and Automata Theory and Applications - 4th International Conference, LATA 2010, Proceedings

T2 - 4th International Conference on Language and Automata Theory and Applications, LATA 2010

Y2 - 24 May 2010 through 28 May 2010

ER -

Chomsky-Schützenberger-type characterization of multiple context-free languages

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this