The size-cost of Boolean operations on constant height deterministic pushdown automata
Тип публикации: Journal Article
Дата публикации: 2012-08-01
scimago Q2
wos Q3
white level БС3
SJR: 0.494
CiteScore: 2.5
Impact factor: 1
ISSN: 03043975, 18792294
Theoretical Computer Science
General Computer Science
Краткое описание
We study the size-cost of Boolean operations on constant height deterministic pushdown automata , i.e., on the traditional pushdown automata with a built-in constant limit on the height of the pushdown. We design a simulation showing that a complement can be obtained with a polynomial tradeoff. For intersection and union, we show an exponential simulation, and prove that the exponential blow-up cannot be avoided.
Найдено
Ничего не найдено, попробуйте изменить настройки фильтра.
Для доступа к списку цитирований публикации необходимо авторизоваться.
Топ-30
Журналы
|
1
2
3
4
5
6
7
|
|
|
Lecture Notes in Computer Science
7 публикаций, 50%
|
|
|
Information and Computation
4 публикации, 28.57%
|
|
|
International Journal of Foundations of Computer Science
1 публикация, 7.14%
|
|
|
Acta Informatica
1 публикация, 7.14%
|
|
|
Journal of Computer and System Sciences
1 публикация, 7.14%
|
|
|
1
2
3
4
5
6
7
|
Издатели
|
1
2
3
4
5
6
7
8
|
|
|
Springer Nature
8 публикаций, 57.14%
|
|
|
Elsevier
5 публикаций, 35.71%
|
|
|
World Scientific
1 публикация, 7.14%
|
|
|
1
2
3
4
5
6
7
8
|
- Мы не учитываем публикации, у которых нет DOI.
- Статистика публикаций обновляется еженедельно.
Вы ученый?
Создайте профиль, чтобы получать персональные рекомендации коллег, конференций и новых статей.
Метрики
14
Всего цитирований:
14
Цитирований c 2025:
0
Цитировать
ГОСТ |
RIS |
BibTex
Цитировать
ГОСТ
Скопировать
Bednárová Z. et al. The size-cost of Boolean operations on constant height deterministic pushdown automata // Theoretical Computer Science. 2012. Vol. 449. pp. 23-36.
ГОСТ со всеми авторами (до 50)
Скопировать
Bednárová Z., Geffert V., Mereghetti C., Palano B. The size-cost of Boolean operations on constant height deterministic pushdown automata // Theoretical Computer Science. 2012. Vol. 449. pp. 23-36.
Цитировать
RIS
Скопировать
TY - JOUR
DO - 10.1016/j.tcs.2012.05.009
UR - https://doi.org/10.1016/j.tcs.2012.05.009
TI - The size-cost of Boolean operations on constant height deterministic pushdown automata
T2 - Theoretical Computer Science
AU - Bednárová, Zuzana
AU - Geffert, Viliam
AU - Mereghetti, Carlo
AU - Palano, Beatrice
PY - 2012
DA - 2012/08/01
PB - Elsevier
SP - 23-36
VL - 449
SN - 0304-3975
SN - 1879-2294
ER -
Цитировать
BibTex (до 50 авторов)
Скопировать
@article{2012_Bednárová,
author = {Zuzana Bednárová and Viliam Geffert and Carlo Mereghetti and Beatrice Palano},
title = {The size-cost of Boolean operations on constant height deterministic pushdown automata},
journal = {Theoretical Computer Science},
year = {2012},
volume = {449},
publisher = {Elsevier},
month = {aug},
url = {https://doi.org/10.1016/j.tcs.2012.05.009},
pages = {23--36},
doi = {10.1016/j.tcs.2012.05.009}
}
Ошибка в публикации?