A Relation Between Unambiguous Regular Expressions and Abstract Data Types

Article type: Research Article

Authors: Preoteasa, Viorel

Affiliations: Department of Computer Science, Academy of Economic Studies, Bucharest, Romania

Note: [] Address for correspondence: Turku Center for Computer Science, DataCity, Lemminkäisenkatu 14 A, FIN-20520 Turku, Finland, email: viorel.preoteasa@abo.fi

Abstract: 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.

Keywords: abstract data types, categorical model, unambiguous regular expressions, finite automata

DOI: 10.3233/FI-1999-40104

Journal: Fundamenta Informaticae, vol. 40, no. 1, pp. 53-77, 1999