Minimization via duality

Bezhanishvili, N. and Kupke, Clemens and Panangaden, Prakash (2012) Minimization via duality. In: Logic, Language, Information and Computation. Lecture Notes in Computer Science, 7456 . Springer, Berlin, pp. 191-205. ISBN 9783642326202

[img]
Preview
 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.

    Author(s):Bezhanishvili, N., Kupke, Clemens and Panangaden, Prakash
    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:05 Jun 2019 04:11
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/45001
    Export data:
    CORE (COnnecting REpositories)