1003988
Solving Systems of Equations over Hypersets
A universe composed by rational ground terms ia characterized (both constructively and axiomatically), where the interpreted set constructs land •ith (the latter designating the element insertion operation) coexist with free Herbrand functors. Ordinary syntactic equivalence must be superseded by an equivalence relation ~. between trees labelled over a signature, that suitably reflects the semantics of vith. Membership (definable as "d E t =oo~ ( t vith d) ~ t") meets the non-well-foundedn,ess property characteristic of hyperset theory. An algorithm for solving the NP-eomplete unification problem pertaining to hollow hyperset terms is provided, and shown to be totally correct. An application to the matching of finite state automata is hinted at. Introduction With this paper we wish to contribute to the field of constraint logic programming mainly in two ways. First, by characterizing hyperseb both constructively and axiomatically ( cf. See. 2, 3); then, by specifying a procedure for normalizing constraints of the most basic kind over hypersets. Our procedure will be shown to always terminate and to give the proper results (cf. Sec. 4). A by-product of our constraint normalization procedure is an algorithm for solving a novel NP-complete unifictJtion problem pertaining to hypersets, which has direct applications on its own: it can be used, for instance, to determine whether two finite state automata characterize the same language (cf. See. 5). Hypersets of the kind we will propose are very intimately related to Aczel's nonwell-founded sets (ef. [1]), but they all have finite cardinality and height; moreover they are hybrid, in that their construction involves free Herbrand fun.etors. The finiteness restriction comes from our willingness to regard hypersets as tnstanees of an algorithmic data structure; the proposed hybridization comes from our goal to Q Until. tli Pi .. , Dip. di Inlonn.atica. Cono ltalia -40, 561~Piaa (1). do'fiertdi .uaipi.il ¢ U~ti•. tli Roma "L. Sa,ienza", Dip. di Inl. e Siat. Via Salaria, 113. 00198-Rom&. o.odeoe .. si.dis.uairo .. l.il 6 Uniw. tli Utli"e, Dip. di Matematica e Inlormatica. Via Zanon, 6. 33l~Udine (1). policrited!.i.1111iad.il • Uftiw. tli Parma, Dip. di Matematica. Via M. D'Azepo, 85/ A. -43l~P.vma (1). 1ro••iep~t.aat~ . 1111ipr . il
18295484
Embedding extensional finite sets in CLP
In this paper we review the definition of {log}1, a logic language with sets, from the viewpoint of CLP. We show that starting with a CLP-scheme allows a more uniform treatment of the built-in set operations (namely, =, ∈ and their negative counterparts), and allows all the theoretical results of CLP to be immediately exploitable. We prove this by precisely defining the privileged interpretation domain and the axioms of the selected set theory. Then we define a non-deterministic procedure for checking constraint satisfiability based on the reduction of a given constraint to a collection of constraint in a suitable canonical form, which is provable to be sound and complete w.r.t. the given theory. Algorithms for trasforming each one of the set constraints the language provides (=, 6=, ∈ and 6∈) into their corresponding canonical forms are described in details. It is also shown that the resulting language is powerful enough to allow all the usual operations on sets (such as ⊆, ∪, etc.) to be effectively programmed in the language itself.
16978187
Set Unification
The unification problem in algebras capable of describing sets has been tackled, directly or indirectly, by many researchers and it finds important applications in various research areas, e.g. deductive databases, theorem proving, static analysis, rapid software prototyping. The various solutions proposed are spread across a large literature. In this paper we provide a uniform presentation of unification of sets, formalizing it at the level of set theory. We address the problem of deciding existence of solutions at an abstract level. This provides also the ability to classify different types of set unification problems. Unification algorithms are uniformly proposed to solve the unification problem in each of such classes. The algorithms presented are partly drawn from the literature – and properly revisited and analyzed – and partly novel proposals. In particular, we present a new goal-driven algorithm for general $ACI1$ unification and a new simpler algorithm for general $(Ab)(C\ell)$ unification.
15589668
Logic Meta-Programming Facilities in 'LOG
A meta-level extension of a logic programming language is presented. The resulting language, called 'LOG (read quote-log), provides meta-programming facilities similar to those of Prolog while preserving a declarative logical semantics. It also offers new meta-programming opportunities as compared with Prolog due to its ability to treat whole programs, i.e. sequences of clauses, as data objects. The extension basically consists in defining a suitable naming scheme. It associates two different but related meta-representations with every syntactic object of the language, from characters to programs. The choice of the double metarepresentation is motivated by both the user and the implementation viewpoints. All Prolog built-in meta-predicates can be redefined as 'LOG programs by exploiting the new naming scheme. Then some syntactic sugar is added to make the language more concrete. Some examples are given, in particular to show the ability of the language to deal with programs as data.
7012937
Integrating Lists, Multisets, and Sets in a Logic Programming Framework
The first order theories of lists, bags, compact-lists (i.e., lists where the number of contiguous occurrences of each element is immaterial), and sets are introduced via axioms. Such axiomatizations are shown to be especially suitable for the integration with free functor symbols governed by the classical Clark’s axioms in the context of Constraint Logic Programming. Adaptations of the extensionality principle to the various theories taken into account is then exploited in the design of unification algorithms for the considered data structures. All the theories presented can be combined providing frameworks to deal with several of the proposed data structures simoultaneously. The unification algorithms proposed can be combined (merged) as well to produce engines for such combination theories.
60140
A uniform approach to constraint-solving for lists, multisets, compact lists, and sets
Lists, multisets, and sets are well-known data structures whose usefulness is widely recognized in various areas of computer science. They have been analyzed from an axiomatic point of view with a parametric approach in Dovier et al. [1998], where the relevant unification algorithms have been developed. In this article, we extend these results considering more general constraints, namely, equality and membership constraints and their negative counterparts.
21945654
Designing Hypermedia Applications with Objects and Patterns
In this paper we present a software engineering approach for building hypermedia applications. Our approach combines the use of an object-oriented method with a system of design patterns for navigational and interface design. We first present the core activities in the Object-Oriented Hypermedia Design Method (OOHDM), namely conceptual design navigation design, abstract interface design and implementation, describing the modeling constructs we use to build high-level, abstract navigational and interface structures. Next we give the rationale for using design patterns in the process of building high quality hypermedia applications, and present some simple patterns solving recurrent design problems. We finally discuss some further issues.
47231847
Enhancing a requirements baseline with scenarios
Scenarios are well recognized as an important strategy towards understanding the interface between the environment and the system, as well as a means to elicit and specify software behavior. We have a broader understanding of scenarios: for us, a scenario is an evolving description of situations in the environment. Our proposal is framed by Leite's (1995) work on a client-oriented requirements baseline, which aims at modeling the external requirements of a software system and its evolution. Scenarios start by describing the environmental situation, according to the main actions performed outside the software system. Scenarios also help the clarification of the interrelation between functional and non-functional requirements. We have validated our strategy and related representations based on case studies of a real situation.
1956133
Enhancing a requirements baseline with scenarios
Scenarios are well recognised as an important strategy towards understanding the interface between the environment and the system as well as a means of eliciting and specifying software behaviour. We adopt a broader view of scenarios. For us, a scenario is an evolving description of situations in the environment. Our proposal is framed by Leite’s work on a client-oriented requirements baseline, which aims to model the external requirements of a software system and its evolution. Scenarios start by describing the environment situations, according to the main actions performed outside the software system. Scenarios also help to clarify the interrelation between functional and non-functional requirements. We have validated our strategy and the related representations based on case studies.
7589770
Specifying Quality Characteristics and Attributes for Websites
In this work, we outline more than a hundred characteristics and attributes for the domain of academic sites in order to analyze the quality requirement tree and a way to specify them. These elements are used in a quantitative methodology for assessment, comparison, and ranking processes. The proposed Web-site Quality Evaluation Methodology (QEM) can be a useful approach to assess the quality in different phases of a Web product life cycle. In the academic study, we have observed three different evaluation audiences regarding visitor users: current and prospective students, academic personnel, and research sponsors. Besides, the aim of this work is to show a hierarchical and descriptive specification framework for characteristics, subcharacteristics and attributes. This framework is a key underlying piece in the construction of a hyperdocumented evaluation tool. Finally, some results are presented and concluding remarks are discussed.