Boolean language operations on nondeterministic automata with a pushdown of constant height

作者：

Highlights：

• We study the size cost of implementing boolean language operations on constant height nondeterministic pushdown automata.

• We show that an exponential size blow up is necessary and sufficient for intersection.

• We provide a linear trade-off for union.

• We provide a double exponential upper bound and a single exponential lower bound for complementation.

摘要

•We study the size cost of implementing boolean language operations on constant height nondeterministic pushdown automata.•We show that an exponential size blow up is necessary and sufficient for intersection.•We provide a linear trade-off for union.•We provide a double exponential upper bound and a single exponential lower bound for complementation.

论文关键词：Descriptional complexity,Finite state automata,Regular languages,Nondeterministic pushdown automata

论文评审过程：Received 15 October 2016, Revised 5 March 2017, Accepted 18 June 2017, Available online 21 July 2017, Version of Record 14 September 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.06.007