文章基本信息

标题：Minimization of visibly pushdown automata is NP-complete
本地全文：下载
作者：Raskin, Michael ; Muscholl, Anca ; Gauwin, Olivier 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2020
卷号：16
期号：1
页码：1-9
语种：English
出版社：Technical University of Braunschweig
摘要：We show that the minimization of visibly pushdown automata is NP-complete.This result is obtained by introducing immersions, that recognize multiplelanguages (over a usual, non-visible alphabet) using a common deterministictransition graph, such that each language is associated with an initial stateand a set of final states. We show that minimizing immersions is NP-complete,and reduce this problem to the minimization of visibly pushdown automata.
关键词：Computer Science ; Formal Languages and Automata Theory