文章基本信息

标题：Representing a P-complete problem by small trellis automata
本地全文：下载
作者：Alexander Okhotin
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2008
卷号：1
页码：185-198
DOI：10.4204/EPTCS.1.18
出版社：Open Publishing Association
摘要：A restricted case of the Circuit Value Problem known as the Sequential NOR Circuit Value Problem was recently used to obtain very succinct examples of conjunctive grammars, Boolean grammars and language equations representing P-complete languages (Okhotin, http://dx.doi.org/10.1007/978-3-540-74593-8_23 "A simple P-complete problem and its representations by language equations", MCU 2007). In this paper, a new encoding of the same problem is proposed, and a trellis automaton (one-way real-time cellular automaton) with 11 states solving this problem is constructed.