Standard

Comparing linear conjunctive languages to subfamilies of the context-free languages. / Okhotin, Alexander.

SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. 2011. p. 431-443 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6543 LNCS).

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

Harvard

Okhotin, A 2011, Comparing linear conjunctive languages to subfamilies of the context-free languages. in SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6543 LNCS, pp. 431-443, 37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011, Novy Smokovec, Slovakia, 22/01/11. https://doi.org/10.1007/978-3-642-18381-2_36

APA

Okhotin, A. (2011). Comparing linear conjunctive languages to subfamilies of the context-free languages. In SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (pp. 431-443). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6543 LNCS). https://doi.org/10.1007/978-3-642-18381-2_36

Vancouver

Okhotin A. Comparing linear conjunctive languages to subfamilies of the context-free languages. In SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. 2011. p. 431-443. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-18381-2_36

Author

Okhotin, Alexander. / Comparing linear conjunctive languages to subfamilies of the context-free languages. SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. 2011. pp. 431-443 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{f6c00a7cf95540078f9fdb668b087403,
title = "Comparing linear conjunctive languages to subfamilies of the context-free languages",
abstract = "Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (Okhotin, {"}On the equivalence of linear conjunctive grammars to trellis automata{"}, RAIRO ITA, 2004), and this family is known to be incomparable to the context-free languages (Terrier, {"}On real-time one-way cellular array{"}, Theoret. Comput. Sci., 1995). This paper investigates subclasses of the context-free languages for possible containment in this class. It is shown that every visibly pushdown automaton (Alur, Madhusudan, {"}Visibly pushdown languages{"}, STOC 2004) can be simulated by a one-way real-time cellular automaton, but already for LL(1) context-free languages and for one-counter DPDAs no simulation is possible.",
author = "Alexander Okhotin",
year = "2011",
month = jan,
day = "26",
doi = "10.1007/978-3-642-18381-2_36",
language = "English",
isbn = "9783642183805",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "431--443",
booktitle = "SOFSEM 2011",
note = "37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011 ; Conference date: 22-01-2011 Through 28-01-2011",

}

RIS

TY - GEN

T1 - Comparing linear conjunctive languages to subfamilies of the context-free languages

AU - Okhotin, Alexander

PY - 2011/1/26

Y1 - 2011/1/26

N2 - Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO ITA, 2004), and this family is known to be incomparable to the context-free languages (Terrier, "On real-time one-way cellular array", Theoret. Comput. Sci., 1995). This paper investigates subclasses of the context-free languages for possible containment in this class. It is shown that every visibly pushdown automaton (Alur, Madhusudan, "Visibly pushdown languages", STOC 2004) can be simulated by a one-way real-time cellular automaton, but already for LL(1) context-free languages and for one-counter DPDAs no simulation is possible.

AB - Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO ITA, 2004), and this family is known to be incomparable to the context-free languages (Terrier, "On real-time one-way cellular array", Theoret. Comput. Sci., 1995). This paper investigates subclasses of the context-free languages for possible containment in this class. It is shown that every visibly pushdown automaton (Alur, Madhusudan, "Visibly pushdown languages", STOC 2004) can be simulated by a one-way real-time cellular automaton, but already for LL(1) context-free languages and for one-counter DPDAs no simulation is possible.

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

U2 - 10.1007/978-3-642-18381-2_36

DO - 10.1007/978-3-642-18381-2_36

M3 - Conference contribution

AN - SCOPUS:78751675091

SN - 9783642183805

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

SP - 431

EP - 443

BT - SOFSEM 2011

T2 - 37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011

Y2 - 22 January 2011 through 28 January 2011

ER -

ID: 41142962