Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951143 | Journal of Computer and System Sciences | 2017 | 26 Pages |
Abstract
We study the cost of Boolean operations on constant height nondeterministic pushdown automata, i.e., on the ordinary pushdown automata with a limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the exponential blow-up is necessary in the worst case. For union, instead, we provide a linear trade-off while, for complement, we show a double exponential simulation and prove a single exponential lower bound. The same gaps for Boolean operations with regular languages have been shown for traditional nondeterministic automata with unrestricted pushdown.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano,