论文标题
可实现的无上下文超级语言
Realizable and Context-Free Hyperlanguages
论文作者
论文摘要
HyperProperties从一组执行跟踪中将常规基于跟踪的语言提升到一组执行。从正式的角度来看，这些是一组单词集，即超级语言。 Hyperaatomata基于抬起以处理超级语言的经典自动机型。已建议有限的高自拟合（NFH）表达常规的超代理。我们研究了常规超级语言的可靠性问题：给定一组语言，可以由NFH精确描述吗？我们表明，对于单身超级语言而言，问题已经很复杂了。 然后，我们超越了常规的超级语言，并研究无上下文的超级语言。我们表明，无上下文的超仪表的自然扩展是高度不可确定的。然后，我们提出了一个精致的模型，即同步超法符号，该模型可以描述有趣的非规范性超构物，同时保留了许多无上下文语法的可决定性。
Hyperproperties lift conventional trace-based languages from a set of execution traces to a set of sets of executions. From a formal-language perspective, these are sets of sets of words, namely hyperlanguages. Hyperautomata are based on classical automata models that are lifted to handle hyperlanguages. Finite hyperautomata (NFH) have been suggested to express regular hyperproperties. We study the realizability problem for regular hyperlanguages: given a set of languages, can it be precisely described by an NFH? We show that the problem is complex already for singleton hyperlanguages. We then go beyond regular hyperlanguages, and study context-free hyperlanguages. We show that the natural extension to context-free hypergrammars is highly undecidable. We then suggest a refined model, namely synchronous hypergrammars, which enables describing interesting non-regular hyperproperties, while retaining many decidable properties of context-free grammars.
