On algebra of languages representable by vertex-labeled graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Igor Grunsky^a ; ^c ; ^{grunsky@iamm.ac.donetsk.ua} ; Igor Potapov^b ; ^{potapov@liverpool.ac.uk} ; Elena Pryanichnikova^c ; ^{ginger701@mail.ru}
• 关键词：Vertex-labeled graphs ; Formal languages ; Kleene algebra
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：6 April, 2012
• 卷：426-427
• 期：Complete
• 页码：42-48
• 文件大小：222 K

摘要

In this paper, we introduce and study an algebra of languages representable by vertex-labeled graphs. The proposed algebra is equipped with three operations: the union of languages, the merging of languages and the iteration. In contrast to Kleene algebra, which is mainly used for edge-labeled graphs, it can adequately represent many properties of languages defined by vertex-labeled graphs and provides a natural translation from vertex-labeled graphs to regular expressions and vice versa.