Definability by Weakly Deterministic Regular Expressions with Counters is Decidable

Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
复制标题

具有计数器的弱确定性正则表达式的可定义性是可判定的

DOI：
10.1007/978-3-662-48057-1_29
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Matthias Niewerth
Matthias Niewerth
中科院分区：
--
文献类型：
--
作者：
Markus Latte;Matthias Niewerth

文献摘要

被引文献

相似文献

我们证明，带有计数器的弱确定性正则表达式 (WDRE)（正如它们在 XML 模式中使用的那样）最多比等效的 DFA 大指数级。因此，给定的 DFA 是否等同于任何 WDRE 的问题可以在 EXPSPACE 中判定。
We show that weakly deterministic regular expressions with counters (WDREs) —as they are used in XML Schema— are at most exponentially larger than equivalent DFAs. As a consequence, the problem, whether a given DFA is equivalent to any WDRE, is decidable in EXPSPACE.