8 citations · 13 across the 14 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.FL2009★ 2 cited
Nondeterministic State Complexity of Positional Addition
Galina Jirásková, Alexander Okhotin
Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved…
cs.CC2009
Representing a P-complete problem by small trellis automata
Alexander Okhotin
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…