Paper Info
Title
Probabilistic automata for computing with words
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, 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 by Qiu and Wang.
Year
DOI
Venue
2006
10.1016/j.jcss.2012.09.002
Journal of Computer and System Sciences
Keywords
DocType
Volume
probabilistic distribution,probabilistic grammar,generalized extension principle,equivalence,crisp input,extension principle,computing with words,probabilistic conditioning,probabilistic grammars.,retraction principle,crisp symbol,probabilistic automaton,generalized extension,special word,probabilistic au- tomata,model of computation,transition probability,probabilistic automata
Journal
79
Issue
ISSN
Citations 
1
0022-0000
4
PageRank 
References 
Authors
0.38
20
3
Name
Order
Citations
PageRank
yongzhi cao16310.56
Lirong Xia2103486.84
Ying Mingsheng385280.04