Fundamenta Informaticae - Volume 91, issue 3-4

Authors: Moreira, Nelma | Reis, Rogério

Article Type: Research Article

Abstract: Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n^{2} log n) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of …automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices. Show more

DOI: 10.3233/FI-2009-0061

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 611-629, 2009

Authors: Mu, Kedian | Liu, Weiru | Jin, Zhi | Lu, Ruqian | Yue, Anbu | Bell, David

Article Type: Research Article

Abstract: Developing a desirable framework for handling inconsistencies in software requirements specifications is a challenging problem. It has been widely recognized that the relative priority of requirements can help developers to make some necessary trade-off decisions for resolving con- flicts. However, for most distributed development such as viewpoints-based approaches, different stakeholders may assign different levels of priority to the same shared requirements statement from their own perspectives. The disagreement in the local levels …of priority assigned to the same shared requirements statement often puts developers into a dilemma during the inconsistency handling process. The main contribution of this paper is to present a prioritized merging-based framework for handling inconsistency in distributed software requirements specifications. Given a set of distributed inconsistent requirements collections with the local prioritization, we first construct a requirements specification with a prioritization from an overall perspective. We provide two approaches to constructing a requirements specification with the global prioritization, including a merging-based construction and a priority vector-based construction. Following this, we derive proposals for handling inconsistencies from the globally prioritized requirements specification in terms of prioritized merging. Moreover, from the overall perspective, these proposals may be viewed as the most appropriate to modifying the given inconsistent requirements specification in the sense of the ordering relation over all the consistent subsets of the requirements specification. Finally, we consider applying negotiation-based techniques to viewpoints so as to identify an acceptable common proposal from these proposals. Show more

Keywords: Inconsistency, Requirements Engineering, Prioritized Merging, Local Prioritization

DOI: 10.3233/FI-2009-0062

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 631-670, 2009