论文标题
Myhill-nerode定理用于高维自动机
Myhill-Nerode Theorem for Higher-Dimensional Automata
论文作者
论文摘要
我们为高维自动机（HDAS）建立了一个Myhill-hearode类型定理，并指出当它具有有限的前缀商时，语言是常规的。 HDA扩展了具有附加结构的标准自动机，从而可以区分交织和并发。我们还介绍了确定性的HDA，并表明并非所有HDA都是可确定的，也就是说，存在确定性HDA无法识别的普通语言。使用我们的定理，我们开发了确定性语言的内部表征。最后，我们开发了Myhill-nearse构建的类似物和具有接口的HDA的确定性。
We establish a Myhill-Nerode type theorem for higher-dimensional automata (HDAs), stating that a language is regular if and only if it has finite prefix quotient. HDAs extend standard automata with additional structure, making it possible to distinguish between interleavings and concurrency. We also introduce deterministic HDAs and show that not all HDAs are determinizable, that is, there exist regular languages that cannot be recognised by a deterministic HDA. Using our theorem, we develop an internal characterisation of deterministic languages. Lastly, we develop analogues of the Myhill-Nerode construction and of determinacy for HDAs with interfaces.
