DCFLs and recursive types

• To: types@dcs.gla.ac.uk
• Subject: DCFLs and recursive types
• From: steck@dcs.edinburgh.ac.uk
• Date: Thu, 16 Mar 1995 12:40:17 +0000 (GMT)
• Approved: types@dcs.gla.ac.uk

Some time ago, John Mitchell mentioned (on one of the ML lists) an
equivalence between deterministic context-free languages (DCFLs) --
those languages that are accepted by a deterministic pushdown
automaton -- and recursive types.  I haven't been able to locate the
reference for this.  I do see in Hopcroft and Ullman a mention of
Emily Friedman relating "monadic recursion schemes" and DCFLs.  Is
that what is meant?  Do DCFLs have a more explicit link to recursive
types?

-- Paul

• Prev: Question: typing with set of most general unifiers
• Next: Covariant Deep Subtyping Reconsidered
• Index(es):
  • Main
  • Thread