Open AccessTypes and automata
Author(s) -
Michael I. Schwartzbach,
Evanthia Kalpazidou Schmidt
Publication year - 1990
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v19i316.6706
Subject(s) - type (biology) , automaton , monotone polygon , equivalence (formal languages) , computer science , theory of computation , class (philosophy) , mathematics , quantum finite automata , theoretical computer science , automata theory , algebra over a field , discrete mathematics , algorithm , pure mathematics , artificial intelligence , ecology , geometry , biology
A hierarchical type system for imperative programming languages gives rise to various computational problems, such as type equivalence, type ordering, etc. We present a particular class of finite automata which are shown to be isomorphic to type equations. All the relevant type concepts turn out to have well-known automata analogues, such as language equality, language inclusion, etc. This provides optimal or best known algorithms for the type system, by a process of translating type equations to automata, solving the analogous problem, and translating the result back to type equations. Apart from suggesting an implementation, this connection lends a certain naturality to our type system. We also introduce a very general form of extended (recursive) type equations which are explained in terms of (monotone) alternating automata. Since types are simply equationally defined trees, these results may have wider applications.