First-order specifications of programmable data types

Citation
Z. Mirkowska et al., First-order specifications of programmable data types, SIAM J COMP, 30(6), 2000, pp. 2084-2096
Citations number
18
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
30
Issue
6
Year of publication
2000
Pages
2084 - 2096
Database
ISI
SICI code
0097-5397(20000418)30:6<2084:FSOPDT>2.0.ZU;2-I
Abstract
We consider first-order specifications together with the restriction to acc ept only programmable algebras as models. We provide a criterion which link s 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 adm its a programmable yet nonreachable model. Moreover, a general method of sh owing the existence of programmable but nonreachable models for a class of first-order specifications is given.