|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040203,
author = {Currie, James and Petersen, Holger
and Robson, John Michael and Shallit, Jeffrey},
title = {Separating Words with Small Grammars},
journal = jalc,
year = 1999,
volume = 4,
number = 2,
pages = {101--110},
keywords = {context-free grammar, descriptional complexity},
abstract = {We study the following problem: given two words $w$ and
$x$, with $|w|, |x| \leq n$, what is the size of the smallest
context-free grammar $G$ which generates exactly one of
$\lbrace w, x \rbrace$? If $|w| \not= |x|$, then we prove
there exists a $G$ separating $w$ from $x$ of size
$O(\log \log n)$, and this bound is best possible.
If $|w| = |x|$, then we get an upper bound on the size of
$G$ of $O(\log n)$, and a lower bound of
$\Omega(\frac{\log n}{\log\log n})$.}
}