Algebraic specifications of computable and semi-computable data structures : (preprint)
Jan Aldert Bergstra, John Vivian Tucker · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1979
We address theoretical issues to do with algebraic specification methods for data structures, particularly the so called hidden function and hidden sort specifications.On giving exact definitions of the computable and semicomputable data structures we show that every computable data structure possesses a (special kind of) finite, equational hidden functions specification and that every semicomputable data structure possesses a (special kind of) finite, equational hidden sorts specification.In passing we answer 5 questions recently posed by S. Kamin and are able to virtually complete the classification of the comparative power of his 27 categories of algebraic specification methods.