Context-Free Languages via Coalgebraic Trace Semantics Export

@incollection{citeulike:3778519, abstract = {We show that, for functors with suitable mild restrictions, the initial algebra in the category of sets and functions gives rise to the final coalgebra in the (Kleisli) category of sets and relations. The finality principle thus obtained leads to the finite trace semantics of non-deterministic systems, which extends the trace semantics for coalgebras previously introduced by the second author. We demonstrate the use of our technical result by giving the first coalgebraic account on context-free grammars, where we obtain generated context-free languages via the finite trace semantics. Additionally, the constructions of both finite and possibly infinite parse trees are shown to be monads. Hence our extension of the application domain of coalgebras identifies several new mathematical constructions and structures.}, author = {Hasuo, Ichiro and Jacobs, Bart}, citeulike-article-id = {3778519}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11548133_14}, citeulike-linkout-1 = {http://www.springerlink.com/content/07nxpela1evpav81}, doi = {10.1007/11548133_14}, journal = {Algebra and Coalgebra in Computer Science}, keywords = {category-theory, coalgebra, computation, languages}, pages = {213--231}, posted-at = {2008-12-12 01:51:50}, priority = {2}, title = {Context-Free Languages via Coalgebraic Trace Semantics}, url = {http://dx.doi.org/10.1007/11548133_14}, year = {2005} }

TY - CHAP ID - citeulike:3778519 L3 - citeulike-article-id:3778519 N2 - We show that, for functors with suitable mild restrictions, the initial algebra in the category of sets and functions gives rise to the final coalgebra in the (Kleisli) category of sets and relations. The finality principle thus obtained leads to the finite trace semantics of non-deterministic systems, which extends the trace semantics for coalgebras previously introduced by the second author. We demonstrate the use of our technical result by giving the first coalgebraic account on context-free grammars, where we obtain generated context-free languages via the finite trace semantics. Additionally, the constructions of both finite and possibly infinite parse trees are shown to be monads. Hence our extension of the application domain of coalgebras identifies several new mathematical constructions and structures. JF - Algebra and Coalgebra in Computer Science EP - 231 TI - Context-Free Languages via Coalgebraic Trace Semantics SP - 213 KW - category-theory KW - coalgebra KW - computation KW - languages AU - Hasuo, Ichiro AU - Jacobs, Bart PY - 2005/// UR - http://dx.doi.org/10.1007/11548133_14 ER -