• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

An 11-state Trellis Automaton for A P-complete Problem

Alexander Okhotin, An 11-state Trellis Automaton for A P-complete Problem. TUCS Technical Reports 850, Turku Centre for Computer Science, 2008.

Abstract:

An 11-state trellis automaton recognizing a P-complete language over the alphabet {<i>a,b</i>} is constructed.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin07f,
  title = {An 11-state Trellis Automaton for A P-complete Problem},
  author = {Okhotin, Alexander},
  number = {850},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2008},
  keywords = {trellis automata, cellular automata, conjunctive grammars, computational complexity, circuit value problem},
  ISBN = {978-952-12-1969-6},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication