[Home] [Publications] [Personal]
Probabilistic automata for computing with words
By Yongzhi Cao, Lirong Xia and Mingsheng Ying.
Submitted to Journal of Computer and System Sciences.
Abstract
Usually, probabilistic automata and probabilistic
grammars have crisp symbols as inputs, which can be viewed as the
formal models of computing with values. In this paper, we first
introduce probabilistic automata and probabilistic grammars for
computing with (some special) words in a probabilistic framework,
where the words are interpreted as probabilistic distributions or
possibility distributions over a set of crisp symbols. By
probabilistic conditioning, we then establish a retraction principle
from computing with words to computing with values for handling
crisp inputs and a generalized extension principle from computing
with words to computing with all words for handling arbitrary
inputs. These principles show that computing with values and
computing with all words can be respectively implemented by
computing with some special words. To compare the transition
probabilities of two near inputs, we also examine some analytical
properties of the transition probability functions of generalized
extensions. Moreover, the retractions and the generalized extensions
are shown to be equivalence-preserving. Finally, we clarify some
relationships among the retractions, the generalized extensions, and
the extensions studied recently by Qiu and Wang.
Paper
Available upon request.