An efficient algorithm for the inclusion problem of a subclass of DPDAs

Ryo Yoshinaka

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

An efficient algorithm for the inclusion problem of a subclass of DPDAs

Ryo Yoshinaka

INF - System Information Sciences

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

Abstract

This paper presents an efficient algorithm solving the inclusion problem of a new subclass of context-free languages. The languages are accepted by the special kind of real-time deterministic pushdown automata, called strongly forward-deterministic pushdown automata, that go to the same state and push the same sequence of stack symbols whenever transition is allowed on the same input symbol. Our algorithm can be applied to efficient identification in the limit of that class from positive data.

Original language	English
Title of host publication	Language and Automata Theory and Applications - Second International Conference, LATA 2008, Revised Papers
Pages	487-498
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-88282-4_44
Publication status	Published - 2008
Event	2nd International Conference on Language and Automata Theory and Applications, LATA 2008 - Tarragona, Spain 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)	0302-9743
ISSN (Electronic)	1611-3349

Conference

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

Access to Document

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

Cite this

Yoshinaka, R. (2008). An efficient algorithm for the inclusion problem of a subclass of DPDAs. In Language and Automata Theory and Applications - Second International Conference, LATA 2008, Revised Papers (pp. 487-498). (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_44

@inproceedings{1833d71103f247b69ec289177878fed9,

title = "An efficient algorithm for the inclusion problem of a subclass of DPDAs",

abstract = "This paper presents an efficient algorithm solving the inclusion problem of a new subclass of context-free languages. The languages are accepted by the special kind of real-time deterministic pushdown automata, called strongly forward-deterministic pushdown automata, that go to the same state and push the same sequence of stack symbols whenever transition is allowed on the same input symbol. Our algorithm can be applied to efficient identification in the limit of that class from positive data.",

author = "Ryo Yoshinaka",

note = "Funding Information: This research was partially supported by a grant from the Global COE Program, “Center for Next-Generation Information Technology based on Knowledge Discovery and Knowledge Federation”, from the Ministry of Education, Culture, Sports, Science and Technology of Japan.; 2nd International Conference on Language and Automata Theory and Applications, LATA 2008 ; Conference date: 13-03-2008 Through 19-03-2008",

year = "2008",

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

language = "English",

isbn = "3540882812",

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

pages = "487--498",

booktitle = "Language and Automata Theory and Applications - Second International Conference, LATA 2008, Revised Papers",

}

Yoshinaka, R 2008, An efficient algorithm for the inclusion problem of a subclass of DPDAs. in Language and Automata Theory and Applications - Second International Conference, LATA 2008, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5196 LNCS, pp. 487-498, 2nd International Conference on Language and Automata Theory and Applications, LATA 2008, Tarragona, Spain, 08/3/13. https://doi.org/10.1007/978-3-540-88282-4_44

An efficient algorithm for the inclusion problem of a subclass of DPDAs. / Yoshinaka, Ryo.
Language and Automata Theory and Applications - Second International Conference, LATA 2008, Revised Papers. 2008. p. 487-498 (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 › peer-review

TY - GEN

T1 - An efficient algorithm for the inclusion problem of a subclass of DPDAs

AU - Yoshinaka, Ryo

N1 - Funding Information: This research was partially supported by a grant from the Global COE Program, “Center for Next-Generation Information Technology based on Knowledge Discovery and Knowledge Federation”, from the Ministry of Education, Culture, Sports, Science and Technology of Japan.

PY - 2008

Y1 - 2008

N2 - This paper presents an efficient algorithm solving the inclusion problem of a new subclass of context-free languages. The languages are accepted by the special kind of real-time deterministic pushdown automata, called strongly forward-deterministic pushdown automata, that go to the same state and push the same sequence of stack symbols whenever transition is allowed on the same input symbol. Our algorithm can be applied to efficient identification in the limit of that class from positive data.

AB - This paper presents an efficient algorithm solving the inclusion problem of a new subclass of context-free languages. The languages are accepted by the special kind of real-time deterministic pushdown automata, called strongly forward-deterministic pushdown automata, that go to the same state and push the same sequence of stack symbols whenever transition is allowed on the same input symbol. Our algorithm can be applied to efficient identification in the limit of that class from positive data.

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:56449123836

SN - 3540882812

SN - 9783540882817

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

SP - 487

EP - 498

BT - Language and Automata Theory and Applications - Second International Conference, LATA 2008, Revised Papers

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

Y2 - 13 March 2008 through 19 March 2008

ER -

Yoshinaka R. An efficient algorithm for the inclusion problem of a subclass of DPDAs. In Language and Automata Theory and Applications - Second International Conference, LATA 2008, Revised Papers. 2008. p. 487-498. (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_44

An efficient algorithm for the inclusion problem of a subclass of DPDAs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this