Minimization via duality
Bezhanishvili, N. and Kupke, Clemens and Panangaden, Prakash; Ong, Luke and de Queiroz, Ruy, eds. (2012) Minimization via duality. In: Logic, Language, Information and Computation. Lecture Notes in Computer Science, 7456 . Springer, ARG, pp. 191-205. ISBN 9783642326202
|
Text (Bezhanishvili-etal-LNCS2012-Minimization-via-duality)
Bezhanishvili_etal_LNCS2012_Minimization_via_duality.pdf Accepted Author Manuscript Download (147kB)| Preview |
Abstract
We show how to use duality theory to construct minimized versions of a wide class of automata. We work out three cases in detail: (a variant of) ordinary automata, weighted automata and probabilistic automata. The basic idea is that instead of constructing a maximal quotient we go to the dual and look for a minimal subalgebra and then return to the original category. Duality ensures that the minimal subobject becomes the maximally quotiented object.
Creators(s): | Bezhanishvili, N., Kupke, Clemens and Panangaden, Prakash; Ong, Luke and de Queiroz, Ruy | Item type: | Book Section |
---|---|
ID code: | 45001 |
Keywords: | boolean algebra, left adjoint, forgetful functor, minimal realization, contravariant functor , Electronic computers. Computer science, Computational Theory and Mathematics |
Subjects: | Science > Mathematics > Electronic computers. Computer science |
Department: | Faculty of Science > Computer and Information Sciences |
Depositing user: | Pure Administrator |
Date deposited: | 25 Sep 2013 14:22 |
Last modified: | 20 Jan 2021 15:31 |
Related URLs: | |
URI: | https://strathprints.strath.ac.uk/id/eprint/45001 |
Export data: |