Treffer: Context-free languages via coalgebraic trace semantics

Title:
Context-free languages via coalgebraic trace semantics
Authors:
HASUO, Ichiro, JACOBS, Bart
Source:
Algebra and coalgebra in computer science (Swansea, 3-6 September 2005)Lecture notes in computer science. :213-231
Publisher Information:
Berlin: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 17 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Théorie programmation, Programming theory, Algèbre processus, Process algebra, Algebra proceso, Approche probabiliste, Probabilistic approach, Enfoque probabilista, Coalgèbre, Coalgebra, Grammaire CF, Context free grammar, Gramática independiente, Langage CF, Context free language, Lenguaje CF, Logique monadique, Monadic logic, Lógica monadica, Non déterminisme, Non determinism, No determinismo, Structure construction, Construction structure, Estructura construcción, Sémantique algébrique, Algebraic semantic, Semántica algebraica, Finalité, Finality, Finalidad
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institute for Computing and Information Sciences, Radboud University Nijmegen, P.O. Box 9010, 6500 GL Nijmegen, Netherlands
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17116002
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17116002
Database:
PASCAL Archive

Weitere Informationen

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