tyeps, type constraint systems, strings, etc
I'll be checking in my notes shortly, but I figured that this wasn't going to fit into a margin...
In section 10.2, you discuss the correspondence between type constraint systems and non-deterministic finite automata.
It seemed from my reading that a type can be read as a (potentially infinite) tree, which in turn can be read as the set of strings that describe all paths from the root to the leaves of the tree. Thus, a type corresponds to a set of strings, or a single language.
In section 10.2, you say that there is a correspondence between type constraint systems and NFAs. But to me, a type constraint system describes not just one type, but rather a (potentially empty) set of types. Therefore, a type constraint system (TCS) corresponds to a set of languages, while an NFA corresponds to a single language.
Can you resolve this confusion for me (preferably by amending the paper with some sort of clarifying note)?
In section 10.2, you discuss the correspondence between type constraint systems and non-deterministic finite automata.
It seemed from my reading that a type can be read as a (potentially infinite) tree, which in turn can be read as the set of strings that describe all paths from the root to the leaves of the tree. Thus, a type corresponds to a set of strings, or a single language.
In section 10.2, you say that there is a correspondence between type constraint systems and NFAs. But to me, a type constraint system describes not just one type, but rather a (potentially empty) set of types. Therefore, a type constraint system (TCS) corresponds to a set of languages, while an NFA corresponds to a single language.
Can you resolve this confusion for me (preferably by amending the paper with some sort of clarifying note)?
posted by pnkfelix at 4:15 PM
1 Comments:
You misspelled tpyes.
A constraint system plus a choice of variable defines a type - such as "the upper bound for TAU in graph C". A transition relation plus a choice of start states defines an automaton - such as "go from q_0 in delta". (Both descriptions elide choice of domains: choice of type constructors and variables vs alphabet and states.) So a constraint set corresponds to a transition relation and a constrained variable (basically a type) corresponds to a full automaton.
I'll try to see how best to fit this into the paper.
Post a Comment
<< Home