Abstract: Formal languages can be extended to include a probability with each string in the set. For Regular (Class 4) and Context-Free (Class 3) Languages, string probabilities follow from probabilities that are assigned to the grammar rules. It's easy to show that a Regular probabilistic grammar is equivalent to a Markov Process. So the Context-Free Probabilistic Grammar (PCFG) produces a probabilistic language that is more complicated than anything a Markov Process can model.

Some basic theory will be explained as well as the equation for finding a language's average string length. We'll see two examples of complicated processes that are modeled by PCFGs, and how the better model improves results. Modeling the "waterfall display", commonly used with sonar, leads to improved blip detection. Modeling internet communications that have statistically dependent packets, leads to improved buffer sizing.

Speaker's Bio:Richard A. Thompson is a professor in, and the director of, the Telecom Program at the University of Pittsburgh. He received his BSEE from Lafayette College, his MSEE from Columbia University, and his PhD in Computer Science from the University of Connecticut. He came to Pitt in 1989 after 20 years at AT&T Bell Laboratories. Dr. Thompson's research interests are: circuit- and packet-switched telephony and photonic switching.