Requirements are more than a set of system level goal-statements, which originate from different viewpoints of stakeholders. We can classify the requirements objectively along several dimensions: users, data, operations, performance, security, etc. There are important relationships among requirements that are based on the relationships among the data and operations. We study the role of these relationships and their implications in requirements engineering, and provide a systematic method for requirements engineering based on the workflow-model and the data-model of the system.

We propose a new domain model for representing software functional requirements that can help the subsequent phases of design, development, and testing. The model consists of a use-relationship between the operations and the data-items and a finite-state model for the valid sequences of those operations. We show how this model can help us in the analysis and structuring of the requirements via the identification of submodels, which in turn can simplify the design and other phases. We also give an algorithm to compute the use-relationship for an object-oriented source-code as a reengineering step for requirements verification. We give several detailed examples.

We present a formal method for designing the class structure based on a partial order on the functions, which is derived from the use-relationship between the functions and the various data items. We can regard this method as an initial step in building a theory of refactoring and design-patterns. Our method can identify the functions which should be factored into subfunctions, including their desired signatures and a reduced use-complexity, in order to simplify the class-subclass structure. A similar remark holds for the decomposition or consolidation of data items as well. We illustrate our method with several examples.

We present here a new way of modelling a complex system by a number of finite-state components which work together by transferring control among them in a fashion similar to the usual function-calls, including recursive calls. This gives us a simpler modelling technique than statecharts, which are often too complex for general users. The new technique also helps to keep the number of states small as in statecharts. We define the semantics of an interacting family of finite-state models in terms of their behavior-trees. As an elegant application of finite-state modelling, we present a maximally efficient controller design for a tree-structured set of tasks in a reactive system by taking advantage of the common computations among the tasks.

Although finite-state models have been used in software modeling for some time, a general method for building and manipulating such models which directly relates to a program's structure is not readily available. We fill this gap by constructing a canonical finite-state model M(P) from the flowchart of a program P. We then present several methods for simplifying M(P) which correspond to creating higher level models for P and to improving P by eliminating its design flaws. Finally, we show that states based on data-values and their abstractions give us greater flexibility in creating finite-state models that can be used in practice to build the models from requirements.

We study the problem of creating a functional design from a dataflow diagram D. We use the domination-relationship on data-items in D to obtain a canonical function calling-scheme S(D) which is optimal in that it uses the minimum number of global variables for the interface among functions, while keeping the function parameters to a minimum. The difficulty of determining a function calling-scheme that is both valid and optimal is because the number of valid calling-schemes is exponentially large in the size of D. We also use S(D) to obtain a decomposition of D into larger single-output function-blocks. In previous work we give an algorithm to generate the basic pseudocode for each function, including its interface, for the calling-scheme S(D).

This is the first part of a three-part series in which we present a new approach to software functional design, starting from the dataflow diagram D of an algorithm. We introduce the notion of a path-closed set for characterizing the subsets of D that can be considered as function blocks for the software. We also define an equivalence relation and a partial order on the data-items in D, which together with the path-closed subsets, give rise to three design rules for creating a functional design. We illustrate our method using an algorithm with complex dataflows and data-structures.

We propose here a new notion of a minimal model for forming circumscription in belief-logic by incorporating the notion of minimal models in the prepositional logic. This results in a new circumscription operation for belief-formulas than the one considered in [4-6]. An important feature of the new circumscription operation is its close relationship with the circumscription of prepositional formulas. For instance, we have CIRC[Bφ] = B(CIRC[φ]), where φ is a prepositional formula. We give several examples to show that the new notion of circumscription fits quite well with intuition.

Computing circumscription of a first-order theory is difficult because it involves, in general, a second-order quantifier. It is therefore important to study the cases where the circumscription can be expressed as a first-order theory. Lifschitz and Rabinov have previously shown that the class of separable theories and the class of collapsible theories have this property. Here, we introduce a new class of theories δ, called finitary theories, for which the circumscription CIRC(δ,P,Q) is given by a first order theory δ ∪ δpc, where δpc is the set of predicate completion formulas for predicates in P defined in a suitable way. There are many finitary theories which are interesting and which do not belong to the class of separable or collapsible theories.

A rectangular dissection is a partition of a rectangular space R into $n \geqslant 1$ disjoint rectangles $\{ {r_1 ,r_2 , \cdots ,r_n } \}$. A $T_ * $-plan is a dissection that is obtained by repeated application of the (1) horizontal, (2) vertical, (3) left-spiral, and (4) right-spiral partitioning operations. Two common ways of representing a $T_ * $-plan are the wall representation $w(D)$ and the subregion-tree representation $t(D)$. It is known [S. Kundu, Comm. ACM, 31 (1988), pp. 752–763] that these two representations are equivalent in that one can be uniquely determined from the other. This paper presents an optimal $O(n)$ algorithm for constructing $t(D)$ from $w(D)$, which improves the previous bound of $O(n^2 )$ in [S. Kundu, Comm. ACM, 31 (1988), pp. 752–763]. The new algorithm is based on a domination relationship among the walls, which is defined here and represented by a digraph $G_w (D)$. The algorithm exploits the disjoint cycle property of $G_w (D)$ and the relationship between the tree $t(D)$ and the transitive reduction of the acyclic digraph obtained by merging the cycles of $G_w (D)$ into distinct nodes. The new method of constructing the tree $t(D)$ by means of the digraph $G_w (D)$ can be applied to an arbitrary class of dissections D that are generated by a finite family of partitioning operations that satisfies certain natural restrictions. The complexity of the algorithm remains $O(n)$ for many such families.

A resolution proof or a derivation of the empty clause from a set of clauses S = {C1, C2, …, Ck} is called a tree resolution if no clause Ci is used in more than one resolvent. We show that an unsatisfiable set of clauses S has a tree resolution proof if and only if there is a general semantic tree for S in which no clause appears in more than one terminal node. As an important application of this result, we derive a simple algorithm for obtaining a tree resolution proof, if one exists. The tree resolution proofs are important because they allow us to obtain the shortest “explanation”.

The notion of a call-return tree is defined to describe the dynamic calling relationship of the procedure and functions in a program execution. It is shown how the call-return tree can be used to compute the live times and the execution times of the various calls made during the execution. The call-return tree can also be used to compute other behavioral metrics such as the depth and height of a call and the number of direct and indirect calls generated from any point. The technique applies uniformly for both nonrecursive and recursive calls. The algorithms take linear time in the length of the source code and the number of calls made during an execution.

We present here an improved algorithm to fmd a key of a relation R(A) on the attributes A The algorithm requires O(lKI.IIF/[) time, where IKI is the size of the key obtained and 1141 is the length of the input specification for the functional dependencies F. The previously known algorithms require O(lA/.llfil)time, which can be an order of magnitude larger if IKI is small compared to l-4

article Analysis of the context dependency of CODASYL find-statements with application to a database program conversion Share on Authors: G. Barbara Demo Dipartimento di Informatica Unversita di Tormo, 42 c M D'Azegho, 10125 Torino, ITALY Dipartimento di Informatica Unversita di Tormo, 42 c M D'Azegho, 10125 Torino, ITALYView Profile , Sukhamay Kundu Computer Science Department, Louisiana State University, Baton Rouge, LA Computer Science Department, Louisiana State University, Baton Rouge, LAView Profile Authors Info & Claims ACM SIGMOD RecordVolume 14Issue 4May 1985 pp 354–361https://doi.org/10.1145/971699.318936Online:01 May 1985Publication History 5citation203DownloadsMetricsTotal Citations5Total Downloads203Last 12 Months5Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A solution method is given for finding an optimum constrained path with applications in program testing.

Given a rooted tree with a positive weight associated with every node, a linear algorithm is presented that will partition the tree into a minimum number of subtrees such that the sum of node weights in no subtree exceed a prespecified value k.

A simple necessary and sufficient condition is given for a degree sequence to be realizable by a graph that contains three mutually edge-disjoint spanning trees.