Standard

Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata. / Jirásková, Galina; Okhotin, Alexander.

Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings. ред. / Mizuho Hoshi; Shinnosuke Seki. Springer Nature, 2018. стр. 441-452 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11088 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаяРецензирование

Harvard

Jirásková, G & Okhotin, A 2018, Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata. в M Hoshi & S Seki (ред.), Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 11088 LNCS, Springer Nature, стр. 441-452, 22nd International Conference on Developments in Language Theory, DLT 2018, Tokyo, Япония, 10/09/18. https://doi.org/10.1007/978-3-319-98654-8_36

APA

Jirásková, G., & Okhotin, A. (2018). Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata. в M. Hoshi, & S. Seki (Ред.), Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings (стр. 441-452). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11088 LNCS). Springer Nature. https://doi.org/10.1007/978-3-319-98654-8_36

Vancouver

Jirásková G, Okhotin A. Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata. в Hoshi M, Seki S, Редакторы, Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings. Springer Nature. 2018. стр. 441-452. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-98654-8_36

Author

Jirásková, Galina ; Okhotin, Alexander. / Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata. Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings. Редактор / Mizuho Hoshi ; Shinnosuke Seki. Springer Nature, 2018. стр. 441-452 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{c8a5745762814e8db73f3cb6dd1f8c74,
title = "Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata",
abstract = "The paper improves several state complexity bounds for input-driven pushdown automata (IDPDA), also known as visibly pushdown automata. For deterministic IDPDA it is proved that the number of states sufficient and in the worst case necessary to represent the reversal of an n-state automaton is exactly if all inputs are assumed to be well-nested, and between and (formula presented) without this restriction, cf. (formula presented) in the literature. For the concatenation of an m-state and an n-state IDPDA, the new lower bound is which is asymptotically tight for well-nested inputs. Without this restriction, the state complexity is between and Finally, it is proved that transforming an n-state nondeterministic IDPDA to a deterministic one requires exactly states, cf. in the literature; the known lower bounds on complementing nondeterministic IDPDA and on transforming them to unambiguous are also improved.",
author = "Galina Jir{\'a}skov{\'a} and Alexander Okhotin",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-98654-8_36",
language = "English",
isbn = "9783319986531",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "441--452",
editor = "Mizuho Hoshi and Shinnosuke Seki",
booktitle = "Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings",
address = "Germany",
note = "22nd International Conference on Developments in Language Theory, DLT 2018 ; Conference date: 10-09-2018 Through 14-09-2018",

}

RIS

TY - GEN

T1 - Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata

AU - Jirásková, Galina

AU - Okhotin, Alexander

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The paper improves several state complexity bounds for input-driven pushdown automata (IDPDA), also known as visibly pushdown automata. For deterministic IDPDA it is proved that the number of states sufficient and in the worst case necessary to represent the reversal of an n-state automaton is exactly if all inputs are assumed to be well-nested, and between and (formula presented) without this restriction, cf. (formula presented) in the literature. For the concatenation of an m-state and an n-state IDPDA, the new lower bound is which is asymptotically tight for well-nested inputs. Without this restriction, the state complexity is between and Finally, it is proved that transforming an n-state nondeterministic IDPDA to a deterministic one requires exactly states, cf. in the literature; the known lower bounds on complementing nondeterministic IDPDA and on transforming them to unambiguous are also improved.

AB - The paper improves several state complexity bounds for input-driven pushdown automata (IDPDA), also known as visibly pushdown automata. For deterministic IDPDA it is proved that the number of states sufficient and in the worst case necessary to represent the reversal of an n-state automaton is exactly if all inputs are assumed to be well-nested, and between and (formula presented) without this restriction, cf. (formula presented) in the literature. For the concatenation of an m-state and an n-state IDPDA, the new lower bound is which is asymptotically tight for well-nested inputs. Without this restriction, the state complexity is between and Finally, it is proved that transforming an n-state nondeterministic IDPDA to a deterministic one requires exactly states, cf. in the literature; the known lower bounds on complementing nondeterministic IDPDA and on transforming them to unambiguous are also improved.

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

U2 - 10.1007/978-3-319-98654-8_36

DO - 10.1007/978-3-319-98654-8_36

M3 - Conference contribution

AN - SCOPUS:85053876150

SN - 9783319986531

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

SP - 441

EP - 452

BT - Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings

A2 - Hoshi, Mizuho

A2 - Seki, Shinnosuke

PB - Springer Nature

T2 - 22nd International Conference on Developments in Language Theory, DLT 2018

Y2 - 10 September 2018 through 14 September 2018

ER -

ID: 41137532