Initial Algebra Semantics for Cyclic Sharing Tree Structures

Computer Science – Logic in Computer Science

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

10.2168/LMCS-6(3:15)2010

Terms are a concise representation of tree structures. Since they can be naturally defined by an inductive type, they offer data structures in functional programming and mechanised reasoning with useful principles such as structural induction and structural recursion. However, for graphs or "tree-like" structures - trees involving cycles and sharing - it remains unclear what kind of inductive structures exists and how we can faithfully assign a term representation of them. In this paper we propose a simple term syntax for cyclic sharing structures that admits structural induction and recursion principles. We show that the obtained syntax is directly usable in the functional language Haskell and the proof assistant Agda, as well as ordinary data structures such as lists and trees. To achieve this goal, we use a categorical approach to initial algebra semantics in a presheaf category. That approach follows the line of Fiore, Plotkin and Turi's models of abstract syntax with variable binding.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Initial Algebra Semantics for Cyclic Sharing Tree Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Initial Algebra Semantics for Cyclic Sharing Tree Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Initial Algebra Semantics for Cyclic Sharing Tree Structures will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-369194

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.