A Relation Between Unambiguous Regular Expressions and Abstract Data Types

Using a categorical model of abstract data types [2, 3, 13, 15], we show, following the Kozen's technique [10] and Tarjan's constructions for a deterministic automaton [16], that if two unambiguous regular expressions define the same regular language, then they represent two isomorphic abstract data types.