Fundamenta Informaticae - Volume 111, issue 3

Authors: Bistarelli, Stefano | Santini, Francesco

Article Type: Research Article

Abstract: We present an extension of the Soft Concurrent Constraint language that allows the non-monotonic evolution of the constraint store. To accomplish this, we introduce some new operations: retract(c) reduces the current store by c, updateX (c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; nask(c) tests if c is not entailed by the store. The new retraction operators also permit to reason about Belief Revision, i.e. the process of changing beliefs to take into account a new piece of information. We present this framework as …a possible solution to the negotiation of resources (e.g. web services and network resource allocation) that need a given Quality of Service (QoS). For this reason we also show the the new operators of the language satisfy the Belief Revision postulates [20], which can be used in the negotiation process. The QoS requirements (expressed as semiring levels) of all the parties should converge on a formal agreement through a negotiation process, which specifies the contract that must be enforced. Show more

Keywords: Soft Constraint Concurrent Programming, Nonmonotonicity, Belief Revision, Quality of Service, Negotiation

DOI: 10.3233/FI-2011-563

Citation: Fundamenta Informaticae, vol. 111, no. 3, pp. 257-279, 2011

Authors: Case, John | Moelius III, Samuel E.

Article Type: Research Article

Abstract: In computability theory, program self-reference is formalized by the not-necessarily-constructive form of Kleene's Recursion Theorem (krt). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task using the self-copy. Interpreted in this way, such self-copying programs have usable self-knowledge. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures. One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in …contrast to a result of Royer, which showed that implementation of if-then-else — a denotational control structure — is complementary to the constructive form of Kleene's Recursion Theorem. Examples of non-denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational. Show more

DOI: 10.3233/FI-2011-564

Citation: Fundamenta Informaticae, vol. 111, no. 3, pp. 281-311, 2011

Authors: Claude, Francisco | Navarro, Gonzalo

Article Type: Research Article

Abstract: Self-indexes aim at representing text collections in a compressed format that allows extracting arbitrary portions and also offers indexed searching on the collection. Current self-indexes are unable of fully exploiting the redundancy of highly repetitive text collections that arise in several applications. Grammar-based compression is well suited to exploit such repetitiveness. We introduce the first grammar-based self-index. It builds on Straight-Line Programs (SLPs), a rather general kind of context-free grammars. If an SLP of n rules represents a text T[1, u], then an SLP-compressed representation of T requires 2n log2 n bits. For that same SLP, our self-index takes …O(n log n) + n log2 u bits. It extracts any text substring of length m in time O((m + h) log n), and finds occ occurrences of a pattern string of length m in time O((m(m + h) + h occ) log n), where h is the height of the parse tree of the SLP. No previous grammar representation had achieved o(n) search time. As byproducts we introduce (i) a representation of SLPs that takes 2n log2 n(1 + o(1)) bits and efficiently supports more operations than a plain array of rules; (ii) a representation for binary relations with labels supporting various extended queries; (iii) a generalization of our self-index to grammar compressors that reduce T to a sequence of terminals and nonterminals, such as Re-Pair and LZ78. Show more

Keywords: Grammar-based Compression, Straight-Line Programs, Self-Indexes, Compressed Text Databases, Highly Repetitive Sequences, Pattern Matching, Data Structures

DOI: 10.3233/FI-2011-565

Citation: Fundamenta Informaticae, vol. 111, no. 3, pp. 313-337, 2011

Authors: Lomuscio, Alessio | Penczek, Wojciech | Solanki, Monika | Szreter, Maciej

Article Type: Research Article

Abstract: We investigate the problem of locally monitoring contract regulated behaviours in agent-based web services. We encode contract clauses in service specifications by using extended timed automata. We propose a non intrusive local monitoring framework along with an API to monitor the fulfillment (or violation) of contractual obligations. A key feature of the framework is that it is fully symbolic thereby providing a scalable solution to monitoring. At runtime execution steps generated by the service are passed as input to the runtime monitor. Conformance of the execution against the service specification is checked using a symbolically represented extended timed automaton. This …allows us to monitor service behaviours over large state spaces generated by multiple, long running contracts. We illustrate our methodology by monitoring a service composition scenario from the vehicle repair domain, and report on the experimental results. Show more

DOI: 10.3233/FI-2011-566

Citation: Fundamenta Informaticae, vol. 111, no. 3, pp. 339-355, 2011