Fundamenta Informaticae - Volume 27, issue 4

Authors: Levene, Mark | Loizou, George

Article Type: Research Article

Abstract: We present an alternative approach to that of Chandra and Harel [5] and Abiteboul and Vianu [1] in considering computable database queries, which are mappings from sets of records to sets of records. In particular, we view a computable database query as being realised via a Turing-computable mapping from strings to strings and an encoding, which encodes the input set of records into an appropriate string. An encoding of a set of records consists of two components: an ordering function, which orders the records in a set as well as the values of each record in the set, and an …isomorphism, which maps the values in the records of the set to strings. An important class of encodings, called free encodings, whose isomorphism has the same semantics as the identity mapping on record values, is also defined. Our analysis of computable database queries elucidates the notion of a computable database query by dealing with the problem of how a database language can be implemented on a standard Turing machine that does not cater directly for mappings from sets of records to sets of records. We carry out our analysis by categorising computable database queries into subclasses and by establishing the relationships that exist amongst these subclasses. We also investigate an equivalence relation on computable database queries; two computable database queries are related if they are realised via the same Turing-computable mapping, say δ. We prove the following interesting result regarding the cardinality of the equivalence class of a computable query with respect to the said equivalence relation: either δ does not realise any computable query, or δ realises exactly one computable query, or δ realises a countably infinite set of computable queries. Our final result shows that, by adding membership queries to the class of encoding-independent computable queries, the closure of the resulting extended class under composition of mappings is the set of all isomorphism-independent computable queries. Show more

DOI: 10.3233/FI-1996-27401

Citation: Fundamenta Informaticae, vol. 27, no. 4, pp. 319-348, 1996

Authors: Corradini, Flavio | Nicola, Rocco De

Article Type: Research Article

Abstract: Three of the rewriting systems used by Degano, De Nicola and Montanari to provide Milner's CCS with a causality based semantics are compared by using also a fourth intermediate one. These rewriting systems have been used to associate Petri nets, Labelled Event Structures and structured sets of partial orderings to CCS terms. It is proved that the four rewriting systems yield computations from which the same causality relations among the executed actions can be extracted, thus it is established that the four partial ordering transitional semantics do coincide.

DOI: 10.3233/FI-1996-27402

Citation: Fundamenta Informaticae, vol. 27, no. 4, pp. 349-383, 1996

Authors: Lobo, Jorge | Uzcátegui, Carlos

Article Type: Research Article

Abstract: This paper describes a change theory based on abductive reasoning. We take the AGM postulates for revisions, expansions and contractions, and Katsuno and Mendelzon postulates for updates and incorporate abduction into them. A key feature of the theory is that presents a unified view of standard change operators and abductive change operators rather than a new and independent change theory for abductive changes. Abductive operators reduce to standard change operators in the limiting cases.

DOI: 10.3233/FI-1996-27403

Citation: Fundamenta Informaticae, vol. 27, no. 4, pp. 385-411, 1996

Authors: Mäkinen, Erkki

Article Type: Research Article

Abstract: This note shows that it is undecidable whether or not an arbitrary context-free grammar is (0,l)-total, i.e., whether or not {0, 1}+ ⊆ g(Szl(G)) holds for an arbitrary context-free grammar G, the left Szilard language Szl(G) of G, and a homomorphism g mapping the labels of G's productions into {0, 1} ∪ {λ}. These considerations are motivated by cryptosystems recently proposed by Andrasiu et al.

Keywords: cryptosystems, Szilard languages, (0,l)-totality

DOI: 10.3233/FI-1996-27404

Citation: Fundamenta Informaticae, vol. 27, no. 4, pp. 413-415, 1996