Minimization via duality

N. Bezhanishvili; Clemens Kupke; Prakash Panangaden

doi:10.1007/978-3-642-32621-9_14

Minimization via duality

N. Bezhanishvili, Clemens Kupke, Prakash Panangaden

Research output: Chapter in Book/Report/Conference proceeding › Chapter

27 Citations (Scopus)

48 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 language	English
Title of host publication	Logic, Language, Information and Computation
Subtitle of host publication	19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3-6, 2012. Proceedings
Editors	Luke Ong, Ruy de Queiroz
Place of Publication	Berlin
Publisher	Springer
Pages	191-205
Number of pages	15
Volume	7456
ISBN (Print)	9783642326202
DOIs	https://doi.org/10.1007/978-3-642-32621-9_14
Publication status	Published - 11 Aug 2012
Event	19th International Workshop, WoLLIC 2012 - Buenos Aires, Argentina Duration: 3 Sept 2012 → 6 Sept 2012

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7456
ISSN (Print)	0302-9743

Conference

Conference	19th International Workshop, WoLLIC 2012
Abbreviated title	WoLLIC 2012
Country/Territory	Argentina
City	Buenos Aires
Period	3/09/12 → 6/09/12

Keywords

boolean algebra
left adjoint
forgetful functor
minimal realization
contravariant functor

Access to Document

10.1007/978-3-642-32621-9_14

Bezhanishvili-etal-LNCS2012-Minimization-via-dualityAccepted author manuscript, 144 KB

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

@inbook{11161db556fc4f01be55daae8c9b5f2c,

title = "Minimization via duality",

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.",

keywords = "boolean algebra, left adjoint, forgetful functor, minimal realization, contravariant functor ",

author = "N. Bezhanishvili and Clemens Kupke and Prakash Panangaden",

year = "2012",

month = aug,

day = "11",

doi = "10.1007/978-3-642-32621-9_14",

language = "English",

isbn = "9783642326202",

volume = "7456 ",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "191--205",

editor = "Luke Ong and {de Queiroz}, Ruy",

booktitle = "Logic, Language, Information and Computation",

note = "19th International Workshop, WoLLIC 2012, WoLLIC 2012 ; Conference date: 03-09-2012 Through 06-09-2012",

}

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 , Lecture Notes in Computer Science, vol. 7456, Springer, Berlin, pp. 191-205, 19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, 3/09/12. https://doi.org/10.1007/978-3-642-32621-9_14

Minimization via duality. / Bezhanishvili, N.; Kupke, Clemens; Panangaden, Prakash.

Logic, Language, Information and Computation : 19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3-6, 2012. Proceedings. ed. / Luke Ong; Ruy de Queiroz. Vol. 7456 Berlin : Springer, 2012. p. 191-205 (Lecture Notes in Computer Science; Vol. 7456).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Minimization via duality

AU - Bezhanishvili, N.

AU - Kupke, Clemens

AU - Panangaden, Prakash

PY - 2012/8/11

Y1 - 2012/8/11

N2 - 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.

AB - 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.

KW - boolean algebra

KW - left adjoint

KW - forgetful functor

KW - minimal realization

KW - contravariant functor

UR - http://www.scopus.com/inward/record.url?scp=84866382907&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-32621-9_14

DO - 10.1007/978-3-642-32621-9_14

M3 - Chapter

AN - SCOPUS:84866382907

SN - 9783642326202

VL - 7456

T3 - Lecture Notes in Computer Science

SP - 191

EP - 205

BT - Logic, Language, Information and Computation

A2 - Ong, Luke

A2 - de Queiroz, Ruy

PB - Springer

CY - Berlin

T2 - 19th International Workshop, WoLLIC 2012

Y2 - 3 September 2012 through 6 September 2012

ER -

Minimization via duality

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this