Open AccessOn Type Definitions with Parameters
Author(s) -
Marvin Solomon
Publication year - 1975
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v4i54.6473
Subject(s) - parameterized complexity , mathematics , type (biology) , equivalence (formal languages) , discrete mathematics , uniformization (probability theory) , conjecture , queue , combinatorics , context (archaeology) , computer science , programming language , markov chain , statistics , biology , paleontology , balance equation , ecology , markov model
This paper analyzes some of the consequences of allowing the definition of parameterized data types in programming languages. A typical use of such types is: type queue(x) = struct (x, ref (queue (x))), intqueue = queue(int). It is shown that the addition of parameters permits the definition of new types not definable without parameters. In particular, the types definable with parameters are closely related to the deterministic context-free languages, whereas the author has previously shown that the types definable without parameters are characterized by the regular (i.e. finite state) languages. An important consequence of this fact is that the type equivalence problem, which is easily solvable in the absence of parameters, becomes equivalent to the (currently open) equivalence problem for deterministic pushdown automata.