文章基本信息

标题：Cyclic Proofs and Jumping Automata
本地全文：下载
作者：Denis Kuperberg ; Laureline Pinault ; Damien Pous 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：150
页码：1-14
DOI：10.4230/LIPIcs.FSTTCS.2019.45
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider a fragment of a cyclic sequent proof system for Kleene algebra, and we see it as a computational device for recognising languages of words. The starting proof system is linear and we show that it captures precisely the regular languages. When adding the standard contraction rule, the expressivity raises significantly; we characterise the corresponding class of languages using a new notion of multi-head finite automata, where heads can jump.
关键词：Cyclic proofs; regular languages; multi-head automata; transducers