Two impossibility theorems on behaviour specification of abstract data types
type: Item
instance of: scholarly article
title: Two impossibility theorems on behaviour specification of abstract data types
zbMATH Open document ID: 0790.68080
DOI: 10.1007/BF01185563
author: Oliver Schoett
published in: Acta Informatica
publication date: 1994-05-10T00:00:00Z
review text: Two kinds of finite specification of the behaviour of a counter data type are proved impossible. We consider the class of data types (many-sorted algebras) behaving like an encapsulated counter that can be observed only by a test for zero. It is shown that no nonempty subclass of this class can be finitely specified in ``observational first-order logic'', which is a variant of first-order logic in which equality may not be used on encapsulated types. Secondly, it is shown that the class cannot be described exactly by a finite specification in first-order logic.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 03B70
zbMATH DE Number: 567330
zbMATH Keywords: behaviour specification
zbMATH Keywords: abstract data types
zbMATH Keywords: many-sorted algebras
zbMATH Keywords: counter data type
zbMATH Keywords: first-order logic
MaRDI profile type: Publication
cites work: Q3919053
cites work: Q3943989
cites work: Observational implementation of algebraic specifications
cites work: Q3862379
cites work: Extended directed graphs, a formalism for structured data and data structures
cites work: Q3792662
cites work: Q4729318
cites work: Q3938468
cites work: On observational equivalence and algebraic specification
cites work: Toward formal development of programs from algebraic specifications: Implementations revisited
cites work: Behavioural correctness of data representations
cites work: Data Type Specification: Parameterization and the Power of Specification Techniques
full work available at URL: https://doi.org/10.1007/bf01185563
OpenAlex ID: W2020817341
description: scientific article; zbMATH DE number 567330