Implicit complexity for coinductive data: a characterization of corecurrence

Details Implicit complexity for coinductive data: a characterization of corecurrence Implicit complexity for coinductive data: a characterization of corecurrence

2012-01-05

arxiv.org/abs/1201.1119v1

EPTCS 75, 2012, pp. 1-14

Computer Science

Computational Complexity

In Proceedings DICE 2011, arXiv:1201.0345

Scientific paper

10.4204/EPTCS.75.1

We propose a framework for reasoning about programs that manipulate coinductive data as well as inductive data. Our approach is based on using equational programs, which support a seamless combination of computation and reasoning, and using productivity (fairness) as the fundamental assertion, rather than bi-simulation. The latter is expressible in terms of the former. As an application to this framework, we give an implicit characterization of corecurrence: a function is definable using corecurrence iff its productivity is provable using coinduction for formulas in which data-predicates do not occur negatively. This is an analog, albeit in weaker form, of a characterization of recurrence (i.e. primitive recursion) in [Leivant, Unipolar induction, TCS 318, 2004].

Affiliated with

Also associated with

No associations

Rating

Implicit complexity for coinductive data: a characterization of corecurrence 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 Implicit complexity for coinductive data: a characterization of corecurrence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implicit complexity for coinductive data: a characterization of corecurrence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-609576