Minimization via duality

N. Bezhanishvili, Clemens Kupke, Prakash Panangaden

Research output: Chapter in Book/Report/Conference proceedingChapter

23 Citations (Scopus)
43 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationLogic, Language, Information and Computation
Subtitle of host publication19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3-6, 2012. Proceedings
EditorsLuke Ong, Ruy de Queiroz
Place of PublicationBerlin
PublisherSpringer
Pages191-205
Number of pages15
Volume7456
ISBN (Print)9783642326202
DOIs
Publication statusPublished - 11 Aug 2012
Event19th International Workshop, WoLLIC 2012 - Buenos Aires, Argentina
Duration: 3 Sep 20126 Sep 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7456
ISSN (Print)0302-9743

Conference

Conference19th International Workshop, WoLLIC 2012
Abbreviated titleWoLLIC 2012
CountryArgentina
CityBuenos Aires
Period3/09/126/09/12

Keywords

  • boolean algebra
  • left adjoint
  • forgetful functor
  • minimal realization
  • contravariant functor

Cite this

Bezhanishvili, N., Kupke, C., & Panangaden, P. (2012). Minimization via duality. In L. Ong, & R. de Queiroz (Eds.), Logic, Language, Information and Computation : 19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3-6, 2012. Proceedings (Vol. 7456 , pp. 191-205). (Lecture Notes in Computer Science; Vol. 7456). Springer. https://doi.org/10.1007/978-3-642-32621-9_14