基于转换的ω-正则表达式合成接受方法

《Formal Aspects of Computing》：Transition?Based Acceptance for ω?Regular Expression Synthesis

　　

摘要AI摘要

要查看此AI生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

与环境保持持续交互的反应式系统通常使用$\omega$-正则语言来建模。这些语言通过无限长度的执行轨迹来描述系统行为，并表示为非确定性Büchi自动机（NBAs）或$\omega$-正则表达式。现有的从NBAs合成表达式的方法仅处理基于状态的接受。这一限制迫使在合成之前将紧凑的基于转换的NBAs转换为更大的基于状态的NBAs。本文介绍了第一种直接从基于转换的NBAs合成$\omega$-正则表达式的方法，从而消除了这种转换的需要。该方法通过将NBA分解为非确定性有限自动机的三元组来工作，同时吸收了现有的基于对的分解方法来处理基于转换的接受。我们证明了我们的分解是正确的，从而确立了该方法的有效性和完整性。我们讨论了该方法的时间和描述复杂性。我们对185个线性时态逻辑公式的实证评估支持了我们的假设；基于转换的合成将后缀大小减少了$4.1$和$1.5$，分别用于递归性和反应性属性。我们还分析了决定基于转换的NBA何时会产生更紧凑表达式的结构因素，并将其发展为一个简单的标准，当应用该标准时，得到的表达式至少与直接基于状态的合成得到的表达式一样紧凑。

AI摘要

AI生成的摘要（实验性）

此摘要是使用自动化工具生成的，未由文章作者撰写或审核。它旨在帮助发现、帮助读者评估相关性，并协助来自相关研究领域的读者理解本文的工作。它旨在补充作者提供的摘要，后者仍然是文章的主要摘要。完整文章仍然是权威版本。点击此处了解更多。

点击此处对摘要的准确性、清晰度和有用性进行评论。这样做将有助于改进和未来重新生成的版本。

要查看此AI生成的纯文本摘要，您必须具有高级访问权限。