Optimal infinite scheduling for multi-priced timed automata

This paper is concerned with the derivation of infinite schedules for timed automata that are in some sense optimal. To cover a wide class of optimality criteria we start out by introducing an extension of the (priced) timed automata model that includes both costs and rewards as separate modelling features. A precise definition is then given of what constitutes optimal infinite behaviours for this class of models. We subsequently show that the derivation of optimal non-terminating schedules for such double-priced timed automata is computable. This is done by a reduction of the problem to the determination of optimal mean-cycles in finite graphs with weighted edges. This reduction is obtained by introducing the so-called corner-point abstraction, a powerful abstraction technique of which we show that it preserves optimal schedules. This work has been mostly done while visiting CISS at Aalborg University in Denmark and has been supported by CISS and by ACI Cortos, a program of the French Ministry of Research.     

Verification of evolving software via component substitutability analysis

This paper presents an automated and compositional procedure to solve the substitutability problem in the context of evolving software systems. Our solution contributes two techniques for checking correctness of software upgrades: (1) a technique based on simultaneous use of over-and under-approximations obtained via existential and universal abstractions; (2) a dynamic assume-guarantee reasoning algorithm—previously generated component assumptions are reused and altered on-the-fly to prove or disprove the global safety properties on the updated system. When upgrades are found to be non-substitutable, our solution generates constructive feedback to developers showing how to improve the components. The substitutability approach has been implemented and validated in the ComFoRT reasoning framework, and we report encouraging results on an industrial benchmark. This is an extended version of a paper, Dynamic Component Substitutability Analysis, published in the Proceedings of the Formal Methods 2005 Conference, Lecture Notes in Computer Science, vol. 3582, by the same authors. This research was sponsored by the National Science Foundation under grant nos. CNS-0411152, CCF-0429120, CCR-0121547, and CCR-0098072, the Semiconductor Research Corporation under grant no. TJ-1366, the US Army Research Office under grant no. DAAD19-01-1-0485, the Office of Naval Research under grant no. N00014-01-1-0796, the ICAST project and the Predictable Assembly from Certifiable Components (PACC) initiative at the Software Engineering Institute, Carnegie Mellon University. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the US government or any other entity.     

Measuring the structural similarity among XML documents and DTDs

Measuring the structural similarity between an XML document and a DTD has many relevant applications that range from document classification and approximate structural queries on XML documents to selective dissemination of XML documents and document protection. The problem is harder than measuring structural similarity among documents, because a DTD can be considered as a generator of documents. Thus, the problem is to evaluate the similarity between a document and a set of documents. An effective structural similarity measure should face different requirements that range from considering the presence and absence of required elements, as well as the structure and level of the missing and extra elements to vocabulary discrepancies due to the use of synonymous or syntactically similar tags. In the paper, starting from these requirements, we provide a definition of the measure and present an algorithm for matching a document against a DTD to obtain their structural similarity. Finally, experimental results to assess the effectiveness of the approach are presented.     

Incremental application of knowledge to continuously arriving time-oriented data

In our previous work, we introduced a computational architecture that effectively supports the tasks of continuous monitoring and of aggregation querying of complex domain meaningful time-oriented concepts and patterns (temporal abstractions), in environments featuring large volumes of continuously arriving and accumulating time-oriented raw data. Examples include provision of decision support in clinical medicine, making financial decisions, detecting anomalies and potential threats in communication networks, integrating intelligence information from multiple sources, etc. In this paper, we describe the general, domain-independent but task-specific problem-solving method underling our computational architecture, which we refer to as incremental knowledge-based temporal abstraction (IKBTA). The IKBTA method incrementally computes temporal abstractions by maintaining persistence and validity of continuously computed temporal abstractions from arriving time-stamped data. We focus on the computational framework underlying our reasoning method, provide well-defined semantic and knowledge requirements for incremental inference, which utilizes a logical model of time, data, and high-level abstract concepts, and provide a detailed analysis of the computational complexity of our approach.     

The Basic Constructive Logic for Negation-Consistency

In this paper, consistency is understood in the standard way, i.e. as the absence of a contradiction. The basic constructive logic B_Kc4, which is adequate to this sense of consistency in the ternary relational semantics without a set of designated points, is defined. Then, it is shown how to define a series of logics by extending B_Kc4 up to minimal intuitionistic logic. All logics defined in this paper are paraconsistent logics.     

‘<Emphasis Type="Italic">if p then q</Emphasis>’ . . . and all that: Logical Elements in Reasoning and Discourse

In this paper we explore differences in use of the so-called ‘logical’ elements of language such as quantifiers and conditionals, and use this to explain differences in performance in reasoning tasks across subject groups with different educational backgrounds. It is argued that quantified sentences are difficult natural bases for reasoning, and hence more prone to elicit variation in reasoning behaviour, because they are chiefly used with a pre-determined domain in everyday speech. By contrast, it is argued that conditional sentences form natural premises because of the function they serve in everyday speech. Implications of this for the role of logic in modelling human reasoning behaviour are briefly considered.     

A survey on the history of transaction management: from flat to grid transactions

Transactions have been around since the Seventies to provide reliable information processing in automated information systems. Originally developed for simple ‘debit-credit’ style database operations in centralized systems, they have moved into much more complex application domains including aspects like distribution, process-orientation and loose coupling. The amount of published research work on transactions is huge and a number of overview papers and books already exist. A concise historic analysis providing an overview of the various phases of development of transaction models and mechanisms in the context of growing complexity of application domains is still missing, however. To fill this gap, this paper presents a historic overview of transaction models organized in several ‘transaction management eras’, thereby investigating numerous transaction models ranging from the classical flat transactions, via advanced and workflow transactions to the Web Services and Grid transaction models. The key concepts and techniques with respect to transaction management are investigated. Placing well-known research efforts in historical perspective reveals specific trends and developments in the area of transaction management. As such, this paper provides a comprehensive, structured overview of developments in the area.     

Continuous State Dynamic Programming via Nonexpansive Approximation

This paper studies fitted value iteration for continuous state numerical dynamic programming using nonexpansive function approximators. A number of approximation schemes are discussed. The main contribution is to provide error bounds for approximate optimal policies generated by the value iteration algorithm.      

Multi-core CPUs,Clusters, and Grid Computing: A Tutorial

The nature of computing is changing and it poses both challenges and opportunities for economists. Instead of increasing clock speed, future microprocessors will have “multi-cores” with separate execution units. “Threads” or other multi-processing techniques that are rarely used today are required to take full advantage of them. Beyond one machine, it has become easy to harness multiple computers to work in clusters. Besides dedicated clusters, they can be made up of unused lab computers or even your colleagues’ machines. Finally, grids of computers spanning the Internet are now becoming a reality.     

Differencing and merging of architectural views

Differencing and merging architectural views is an important activity in software engineering. However, existing approaches are still based on restrictive assumptions, such as requiring view elements to have unique identifiers or exactly matching types, which is often not the case in many application domains. We propose an approach based on structural information. We generalize a published polynomial-time tree-to-tree correction algorithm that detects inserts, renames and deletes, into a novel algorithm that additionally detects restricted moves. Our algorithm also supports forcing and preventing matches between view elements. We incorporate the algorithm into tools to compare and merge Component-and-Connector (C&C) architectural views. We provide an empirical evaluation of the algorithm. We illustrate the tools using extended examples, and use them to detect and reconcile interesting differences between real architectural views. This article is an expanded version of the following paper: Abi-Antoun, M., Aldrich, J., Nahas, N., Schmerl, B., and Garlan, D: 2006, ‘Differencing and Merging of Architectural Views’. In: Proceedings of the 21st IEEE International Conference on Automated Software Engineering, pp. 47–58.