|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010403,
author = {Rainer Kemp},
title = {On Prefixes of Formal Languages and Their Relation to the
Average-Case Complexity of the Membership Problem},
journal = jalc,
year = 1996,
volume = 1,
number = 4,
pages = {259--303},
keywords = {formal languages, membership problem,
average-case analysis},
abstract = {Given a formal language ${\cal{L}}$ over an alphabet
furnished with a probability distribution, we shall present
a simple general approach to the computation of the average
length of the shortest prefix which has to be read in order
to decide whether or not a given word of length $n$ belongs
to ${\cal{L}}$. This approach covers a complete average-case
analysis of that parameter, including higher moments about
the origin and the cumulative distribution function. We
shall demonstrate our results by discussing various concrete
languages, such as regular sets, Dyck sets, permutations,
well-known languages encoding trees, etc.}
}