文章基本信息

标题：Recognizable Graph Languages for Checking Invariants
本地全文：下载
作者：Christoph Blume ; Sander Bruggink ; Barbara König 等
期刊名称：Electronic Communications of the EASST
电子版ISSN：1863-2122
出版年度：2010
卷号：29
语种：English
出版社：European Association of Software Science and Technology (EASST)
摘要：We generalize the order-theoretic variant of the Myhill-Nerode theorem to graph languages, and characterize the recognizable graph languages as the class of languages for which the Myhill-Nerode quasi order is a well quasi order. In the second part of the paper we restrict our attention to graphs of bounded interface size, and use Myhill-Nerode quasi orders to verify that, for such bounded graphs, a recognizable graph property is an invariant of a graph transformation system. A recognizable graph property is a recognizable graph language, given as an automaton functor. Finally, we present an algorithm to approximate the Myhill-Nerode ordering.