First-order specifications of programmable data types

We consider first-order specifications together with the restriction to accept only programmable algebras as models. We provide a criterion which links this approach with the "generation principle": all programmable models of any specification SP that meets this criterion are reachable. We...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2001-01, Vol.30 (6), p.2084-2096
Main Authors: MIRKOWSKA, Grazyna, SALWICKI, Andrzej, SREBRNY, Marian, TARLECKI, Andrzej
Format: Article
Language:English
Subjects:
Algebra
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
Computer science
control theory
systems
Data processing. List processing. Character string processing
Exact sciences and technology
Informatics
Memory organisation. Data processing
Semantics
Software
Software engineering
Theoretical computing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider first-order specifications together with the restriction to accept only programmable algebras as models. We provide a criterion which links this approach with the "generation principle": all programmable models of any specification SP that meets this criterion are reachable. We also show an example of a specification which does not satisfy the criterion and admits a programmable yet nonreachable model. Moreover, a general method of showing the existence of programmable but nonreachable models for a class of first-order specifications is given.
ISSN:0097-5397
1095-7111
DOI:10.1137/s0097539797322528