Representing a P-complete problem by small trellis automata
Alexander Okhotin
Electronic Proceedings in Theoretical Computer Science · 2009
doi:10.4204/eptcs.1.18 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
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.
Abstract licence: CC BY-NC-ND
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.