Universal aspects of probabilistic automata (bibtex)

by Lutz Schröder and Paulo Mateus

Abstract:

For lack of composability of their morphisms, probability spaces, and hence probabilistic automata, fail to form categories; however, they fit into the more general framework of precategories, which are introduced and studied here. In particular, the notion of adjunction and weak adjunction for precategories is presented and justified in detail. As an immediate benefit, a concept of (weak) product for precategories is obtained. Thus, universal properties can be used for characterizing well-known basic constructions in the theory of probabilistic automata: The aggregation of two automata is shown to be a weak product, whereas restriction and interconnection of automata are recognized as Cartesian lifts. Finally, we establish that the precategory of decision trees is coreflexive in the precategory of probabilistic automata.

Reference:

Lutz Schröder and Paulo Mateus: Universal aspects of probabilistic automata, In Math. Struct. Comput. Sci., 12, pp. 481–512, 2002. [preprint]

Bibtex Entry:

@Article{SchroderMateus02,
  author = {Lutz Schr{\"o}der and Paulo Mateus},
  title = {Universal aspects of probabilistic automata},
  year = {2002},
  journal = {Math. Struct. Comput. Sci.},
  volume = {12},
  pages = {481--512},
  keywords = {precategory probabilistic automaton adjunction decision tree},
  comment = {<a href="http://www8.informatik.uni-erlangen.de/~schroeder/papers/MSCS1.ps">[preprint]</a>},
  abstract = {For lack of composability of their morphisms, probability spaces, and hence probabilistic automata, fail to form categories; however, they fit into the more general framework of precategories, which are introduced and studied here. In particular, the notion of adjunction and weak adjunction for precategories is presented and justified in detail. As an immediate benefit, a concept of (weak) product for precategories is obtained. Thus, universal properties can be used for characterizing well-known basic constructions in the theory of probabilistic automata: The aggregation of two automata is shown to be a weak product, whereas restriction and interconnection of automata are recognized as Cartesian lifts. Finally, we establish that the precategory of decision trees is coreflexive in the precategory of probabilistic automata.
},
}