A simple P complete problem and its representations by language equations

A simple P-complete problem and its representations by language equations Alexander Okhotin University of Turku and Academy of Finland September 13, 2007 Alexander Okhotin Simple P-complete problem and language equations September 13, 2007 1 / 16

• representing hardest


• linear context-free


• language equations


• problem find small


• trellis automata