On the Complexity of Deciding Call-by-Need

Details On the Complexity of Deciding Call-by-Need On the Complexity of Deciding Call-by-Need

2009-01-07

arxiv.org/abs/0901.0869v2

Computer Science

Logic in Computer Science

Scientific paper

In a recent paper we introduced a new framework for the study of call by need computations to normal form and root-stable form in term rewriting. Using elementary tree automata techniques and ground tree transducers we obtained simple decidability proofs for classes of rewrite systems that are much larger than earlier classes defined using the complicated sequentiality concept. In this paper we show that we can do without ground tree transducers in order to arrive at decidability proofs that are phrased in direct tree automata constructions. This allows us to derive better complexity bounds.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Deciding Call-by-Need 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 On the Complexity of Deciding Call-by-Need, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Deciding Call-by-Need will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-61702