About yes/no queries against possibilistic databases

This article is concerned with the handling of imprecise information in databases. The need for dealing with imprecise data is more and more acknowledged in order to cope with real data, even if commercial systems are most of the time unable to manage them. Here, the possibilistic setting is taken into consideration because it is less demanding than the probabilistic one. Then, any imprecise piece of information is modeled as a possibility distribution intended for constraining the more or less acceptable values. Such a possibilistic database has a natural interpretation in terms of a set of regular databases, which provides the basic gateway to interpret queries. However, if this approach is sound, it is not realistic, and it is necessary to consider restricted queries for which a calculus grounded on the possibilistic database, that is, where the operators work directly on possibilistic relations, is feasible. Extended yes/no queries are dealt with here, where their general form is: “to what extent is it possible and certain that tuple t (given) belongs to the answer to Q,” where Q is an algebraic relational query. A strategy for processing such queries efficiently is proposed under some assumptions as to the operators appearing in Q. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 691–721, 2007.     

A relativistic temporal algebra for efficient design of distributed systems

Adequate methods for checking the specification and design of distributed systems must allow for reasoning about asynchronous activities; efficient methods must perform the reasoning in polynomial time. This paper lays the groundwork for such an efficient deductive system by providing a very general temporal relation algebra that can be used by constraint propagation techniques to perform the required reasoning. Major choices exist when selecting an appropriate temporal model: discrete/dense, linear/nonlinear, and point/interval. James Allen and others have indicated the possible atomic relations between two intervals for the dense-linear-interval model, while Anger, Ladkin, and Rodriguez have shown those needed for a dense-branching-interval model. Rodriguez and Anger further developed a dense-relativistic-interval model based on Lamport'sprecede andcan affect arrows, determining a large number of atomic relations. This paper shows that those same atomic relations are exactly the correct ones for intervals in dense relativistic space-time if intervals are taken as pairs of points (E _s ,E _f ) in space-time such that it is possible to move fromE _s toE _f at less than the speed of light. The relations are defined and named consistently with the earlier work of Rodriguez and Anger, and the relationship between the two models is pursued. The relevance of the results to the verification of distributed specifications and algorithms is discussed.     

An interval‐based temporal algebra based on binary encoding of point relations

This paper presents a method for representing temporal interval relations using a bit‐encoded form of the relationships between interval end points. The set of bit patterns for each interval relationship yields a unique, single‐byte signature that forms the basis of a binary temporal algebra. Also presented is a matrix multiplication algorithm for computing transitive relations based on the definition of sum and product operations for the bit‐encoded relation signatures. This bit‐encoding encompasses the representation of unknown relations between end points of two intervals and captures ambiguities within a temporal system while providing an efficient binary algebra. Finally, an algorithm to compute the transitive closure over a set of intervals forming a temporal system is presented. The algorithm's complexity is analyzed and is O(n³), worst case, where n is the number of temporal intervals within the system. Empirical observations indicate that the closure algorithm completes in O(n²) time, on average. The small memory footprint for the bit‐code, the algorithmic transitive relation calculation, and the closure algorithm, together, form an efficient method for providing machine‐based temporal reasoning capabilities. ©2000 John Wiley & Sons, Inc.     

A Comparison of Inferences about Containers and Surfaces in Small-Scale and Large-Scale Spaces

Inference mechanisms about spatial relations constitute an important aspect of spatial reasoning as they allow users to derive unknown spatial information from a set of known spatial relations. When formalized in the form of algebras, spatial-relation inferences represent a mathematically sound definition of the behavior of spatial relations, which can be used to specify constraints in spatial query languages. Current spatial query languages utilize spatial concepts that are derived primarily from geometric principles, which do not necessarily match with the concepts people use when they reason and communicate about spatial relations. This paper presents an alternative approach to spatial reasoning by starting with a small set of spatial operators that are derived from concepts closely related to human cognition. This cognitive foundation comes from the behavior of image schemata, which are cognitive structures for organizing people's experiences and comprehension. From the operations and spatial relations of a small-scale space, a container–surface algebra is defined with nine basic spatial operators—inside, outside, on, off, their respective converse relations—contains, excludes, supports, separated_from, and the identity relation equal. The container–surface algebra was applied to spaces with objects of different sizes and its inferences were assessed through human-subject experiments. Discrepancies between the container–surface algebra and the human-subject testing appear for combinations of spatial relations that result in more than one possible inference depending on the relative size of objects. For configurations with small- and large-scale objects larger discrepancies were found because people use relations such as part of and at in lieu of in. Basic concepts such as containers and surfaces seem to be a promising approach to define and derive inferences among spatial relations that are close to human reasoning.     

A knowledge server for reasoning about temporal constraints between classes and instances of events

Reasoning with temporal constraints is a ubiquitous issue in many computer science tasks, for which many dedicated approaches have been and are being built. In particular, in many areas, including planning, workflow, guidelines, and protocol management, one needs to represent and reason with temporal constraints between classes of events (e.g., between the types of actions needed to achieve a goal) and temporal constraints between instances of events (e.g., between the specific actions being executed). The temporal constraints between the classes of events must be inherited by the instances, and the consistency of both types of constraints must be checked. In this article, we design a general‐purpose domain‐independent knowledge server dealing with these issues. In particular, we propose a formalism to represent temporal constraints, and we point out two orthogonal parameters that affect the definition of reasoning algorithms operating on them. We then show four algorithms to deal with inheritance and to perform temporal consistency checking (depending on the parameters) and we study their properties. Finally, we report the results we obtained by applying our system to the treatment of temporal constraints in clinical guidelines. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 919–947, 2004.     

A new approach to mining fuzzy databases using nearest neighbor classification by exploiting attribute hierarchies

Data classification is a well‐organized operation in the field of data mining. This article presents an application of the k‐nearest neighbor classification technique for mining a fuzzy database. We consider a data set in which attribute values have certain similarities in nature and analyze the observations for the domain of each attribute, on the basis of fuzzy similarity relations. The proposed technique is general and the presented case study demonstrates the suitability of using this fuzzy approach for mining fuzzy databases, especially when the database contains various levels of abstraction. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 1277–1290, 2004.     

Assessment of four modifications of a novel indexing technique for case‐based reasoning

In this article, we investigate four variations (D‐HS^M, D‐HS^W, D‐HS^E, and D‐HS^EW) of a novel indexing technique called D‐HS designed for use in case‐based reasoning (CBR) systems. All D‐HS modifications are based on a matrix of cases indexed by their discretized attribute values. The main differences between them are in their attribute discretization stratagem and similarity determination metric. D‐HS^M uses a fixed number of intervals and simple intersection as a similarity metric; D‐HS^W uses the same discretization approach and a weighted intersection; D‐HS^E uses information gain to define the intervals and simple intersection as similarity metric; D‐HS^EW is a combination of D‐HS^E and D‐HS^W. Benefits of using D‐HS include ease of case and similarity knowledge maintenance, simplicity, accuracy, and speed in comparison to conventional approaches widely used in CBR. We present results from the analysis of 20 case bases for classification problems and 15 case bases for regression problems. We demonstrate the improvements in accuracy and/or efficiency of each D‐HS modification in comparison to traditional k‐NN, R‐tree, C4,5, and M5 techniques and show it to be a very attractive approach for indexing case bases. We also illuminate potential areas for further improvement of the D‐HS approach. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 353–383, 2007.     

Toward a comprehensive treatment of temporal constraints about periodic events

In this article, we propose an Allen‐like approach to deal with different types of temporal constraints about periodic events. We consider the different components of such constraints (thus, unlike Allen, we also take into account quantitative constraints) including frame times, user‐defined periods, qualitative temporal constraints, and numeric quantifiers and the interactions between such components. We propose a specialized high‐level formalism to represent temporal constraints about periodic events; temporal reasoning on the formalism is performed by a path‐consistency algorithm repeatedly applying our operations of inversion, intersection, and composition and by a specialized reasoner about periods and numeric quantification. The high‐level formalism has been designed in such a way that different types of temporal constraints about periodic events can be represented in a compact and (hopefully) user‐friendly way and path‐consistency‐based temporal reasoning on the formalism can be performed in polynomial time. We also prove that our definitions of inversion, intersection, and composition and, thus, of our path‐consistency algorithm, are correct. This article also sketches the general architecture of the temporal manager for periodic events (TeMP⁺), that has been designed on the basis of our approach. As a working example, we show an application of our approach to scheduling in a school. © 2003 Wiley Periodicals, Inc.     

Spatial Reasoning About Points in a Multidimensional Setting

For n 1, we consider the possible relations between two points of the Euclidean space of dimension n. We define the n-point algebra on the pattern of the point algebra and the cardinal algebra. Generalizing the concept of convexity just as the one of preconvexity, we prove that the consistency problem of convex n-point networks is polynomial for n 1, whereas the consistency problem of preconvex n-point networks is NP-complete for n 3. We characterize a subset of the set of all preconvex relations: the set of all strongly preconvex relations, which contains the set of all convex relations. We demonstrate that the consistency problem of strongly preconvex n-point networks can be decided in polynomial time by means of the weak path-consistency method for all n 1. For n = 3 the set of all strongly preconvex relations is a maximal tractable subclass of the set of all n-point relations. Finally, we prove that the concept of strong preconvexity corresponds to the one of ORD-Horn representability.     

Real space process algebra

The real time process algebra of Baeten and Bergstra [Formal Aspects of Computing,3, 142–188 (1991)] is extended to real space by requiring the presence of spatial coordinates for each atomic action, in addition to the required temporal attribute. It is found that asynchronous communication cannot easily be avoided. Based on the state operators of Baeten and Bergstra [Information and Computation,78, 205–245 (1988)] and following Bergstra et al. [Proc. Seminar on Concurrency, LNCS 197, Springer, 1985, pp. 76–95], asychronous communication mechanisms are introduced as an additional feature of real space process algebra. The overall emphasis is on the introductory explanation of the features of real space process algebra, and characteristic examples are given for each of these.     

Some types of filters in BL algebras

In this paper we introduce some types of filters in a BL algebra A, and we state and prove some theorems which determine the relationship between these notions and other filters of a BL algebra, and by some examples we show that these notions are different. Also we consider some relations between these filters and quotient algebras that are constructed via these filters.     

Mining predecessor–successor rules from DAG data

Data mining extracts implicit, previously unknown, and potentially useful information from databases. Many approaches have been proposed to extract information, and one of the most important ones is finding association rules. Although a large amount of research has been devoted to this subject, none of it finds association rules from directed acyclic graph (DAG) data. Without such a mining method, the hidden knowledge, if any, cannot be discovered from the databases storing DAG data such as family genealogy profiles, product structures, XML documents, task precedence relations, and course structures. In this article, we define a new kind of association rule in DAG databases called the predecessor–successor rule, where a node x is a predecessor of another node y if we can find a path in DAG where x appears before y. The predecessor–successor rules enable us to observe how the characteristics of the predecessors influence the successors. An approach containing four stages is proposed to discover the predecessor–successor rules. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 621–637, 2006.     

A complete temporal relational algebra

Various temporal extensions to the relational model have been proposed. All of these, however, deviate significantly from the original relational model. This paper presents a temporal extension of the relational algebra that is not significantly different from the original relational model, yet is at least as expressive as any of the previous approaches. This algebra employs multidimensional tuple time-stamping to capture the complete temporal behavior of data. The basic relational operations are redefined as consistent extensions of the existing operations in a manner that preserves the basic algebraic equivalences of the snapshot (i.e., conventional static) algebra. A new operation, namely temporal projection, is introduced. The complete update semantics are formally specified and aggregate functions are defined. The algebra is closed, and reduces to the snapshot algebra. It is also shown to be at least as expressive as the calculus-based temporal query language TQuel. In order to assess the algebra, it is evaluated using a set of twenty-six criteria proposed in the literature, and compared to existing temporal relational algebras. The proposed algebra appears to satisfy more criteria than any other existing algebra. Edited by Wesley Chu. Received February 1993 / Accepted April 1995     

A novel group decision model based on mean–variance–skewness concepts and interval-valued fuzzy sets for a selection problem of the sustainable warehouse location under uncertainty

Recently, sustainable warehouse location has been regarded as one of the most critical and significant decision problems for long-term planning in the supply chain. This strategic decision can be effected by different quantitative and qualitative evaluation criteria via three dimensions of the sustainability. Main theme of the paper is to select the most optimal location decision from a number of potential sustainable warehouse candidates. For this purpose, this paper presents a novel multi-criteria decision-making model by a group of supply chain experts or decision makers with interval-valued fuzzy setting and asymmetric uncertainty information. Concepts of mean, variance and skewness are introduced into the proposed group decision model, and their mathematical relations are defined based on a fuzzy possibilistic statistical approach. Then, new relations in this model are presented for obtaining ideal solutions under uncertainty with two high and low values of the possibilistic mean and possibilistic standard deviation, along with the possibilistic cube root of skewness. In addition, novel separation measures and new fuzzy ranking index of hybridized relative closeness coefficients are presented to provide final preference order of warehouse location candidates under uncertain conditions. Finally, a sustainable warehouse location selection problem in a pharmaceutical company is presented and solved by the proposed group decision model to demonstrate its applicability and suitability.

     

Sample-path analysis of stochastic discrete-event systems

This paper presents a unified sample-path approach for deriving distribution-free relations between performance measures for stochastic discrete-event systems extending previous results for discrete-state processes to processes with a general state space. A unique feature of our approach is that all our results are shown to follow from a single fundamental theorem: the sample-path version of the renewal-reward theorem (Y=X). As an elementary consequence of this theorem, we derive a version of the rate-conservation law under conditions more general than previously given in the literature. We then focus on relations between continuous-time state frequencies and frequencies at the points of an imbedded point process, giving necessary and sufficient conditions for theASTA (Arrivals See Time Averages), conditionalASTA, and reversedASTA properties. In addition, we provide a unified approach for proving various relations involving forward and backward recurrence times. Finally, we give sufficient conditions for rate stability of an input-output system and apply these results to obtain an elementary proof of the relation between the workload and attained-waiting-time processes in aG/G/l queue.Research was partially supported by the National Science Foundation under Grant no. DDM-8719825. The government of the United States of America has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research of this author was also partially supported by a grant from Centre International des Étudiants et Stagiares (C.I.E.S.) while he was visiting INRIA, Sophia-Antipolis, Valbonne, France (1991–92).     

Peirce algebras

We present a two-sorted algebra, called aPeirce algebra, of relations and sets interacting with each other. In a Peirce algebra, sets can combine with each other as in a Boolean algebra, relations can combine with each other as in a relation algebra, and in addition we have both a set-forming operator on relations (the Peirce product of Boolean modules) and a relation-forming operator on sets (a cylindrification operation). Two applications of Peirce algebras are given. The first points out that Peirce algebras provide a natural algebraic framework for modelling certain programming constructs. The second shows that the so-calledterminological logics arising in knowledge representation have evolved a semantics best described as a calculus of relations interacting with sets.     

Representation and Reasoning with Multi-Point Events

Allen's Interval Algebra (IA) and Vilain & Kautz's Point Algebra (PA) consider an interval and a point as basic temporal entities (i.e., events) respectively. However, in many situations we need to deal with recurring events that include multiple points, multiple intervals or combinations of points and intervals. In this paper, we present a framework to model recurring events as multi-point events (MPEs) by extending point algebra. The reasoning tasks are formulated as binary constraint satisfaction problems. We propose a polynomial time algorithm (based on van Beek's algorithm) for finding all feasible relations. For the problem of finding a consistent scenario, we propose a backtracking method with a local search heuristic. We also describe an implementation and a detail empirical evaluation of the proposed algorithms. Our empirical results indicate that the MPE-based approach performs better than the existing approaches.     

Building and using temporal knowledge in archaeological documentation

Our previous work on specialized digital libraries showed that each expert was brought to enrich the documentary corpus with his/her point of view (expressed by a model of knowledge). These points of view can be contradictory and therefore, it would be interesting to provide expert communities with tools, enabling them to point out meaning dissensions. In Archaeology, the comparison between different temporal models of knowledge make possible the publication of relative models of knowledge. These different models tend towards the emerging of a global knowledge shared by a community. In this paper we present a method and a set of concrete relations proposed to the annotator, which allows to extend some existing models of knowledge and to build new temporal knowledge. The proposed model, based on temporal algebra relations, permits the use of some efficient constraint propagation algorithms to extract new information.

Spline collocation method with four parameters for solving a system of fourth-order boundary-value problems

In this paper, a spline collocation method is applied to solve a system of fourth-order boundary-value problems associated with obstacle, unilateral and contact problems. The presented method is dependent on four collocation points to be satisfied by four parameters θ _j ∈(0, 1], j=1(1) 4 in each subinterval. It turns out that the proposed method when applied to the concerned system is a fourth-order convergent method and gives numerical results which are better than those produced by other spline methods [E.A. Al-Said and M.A. Noor, Finite difference method for solving fourth-order obstacle problems, Int. J. Comput. Math. 81(6) (2004), pp. 741–748; F. Geng and Y. Lin, Numerical solution of a system of fourth order boundary value problems using variational iteration method, Appl. Math. Comput. 200 (2008), pp. 231–241; J. Rashidinia, R. Mohammadi, R. Jalilian, and M. Ghasemi, Convergence of cubic-spline approach to the solution of a system of boundary-value problems, Appl. Math. Comput. 192 (2007), pp. 319–331; S.S. Siddiqi and G. Akram, Solution of the system of fourth order boundary value problems using non polynomial spline technique, Appl. Math. Comput. 185 (2007), pp. 128–135; S.S. Siddiqi and G. Akram, Numerical solution of a system of fourth order boundary value problems using cubic non-polynomial spline method, Appl. Math. Comput. 190(1) (2007), pp. 652–661; S.S. Siddiqi and G. Akram, Solution of the system of fourth order boundary value problems using cubic spline, Appl. Math. Comput. 187(2) (2007), pp. 1219–1227; Siraj-ul-Islam, I.A. Tirmizi, F. Haq, and S.K. Taseer, Family of numerical methods based on non-polynomial splines for solution of contact problems, Commun. Nonlinear Sci. Numer. Simul. 13 (2008), pp. 1448–1460]. Moreover, the absolute stability properties appear that the method is A-stable. Two numerical examples (one for each case of boundary conditions) are given to illustrate practical usefulness of the method developed.     

Application of bacteria foraging algorithm in designing log periodic dipole array for entire UHF TV spectrum

In this article, an attempt has been made to revisit the design of well‐established log periodic dipole array (LPDA) in light of recent optimization technique, the bacteria foraging algorithm (BFA). Although there are many works published in the literatures based on various optimization techniques, this article deals with the optimization of the LPDA for the entire ultra high frequency (UHF) television (TV) spectrum (470–870 MHz) covering 400 MHz bandwidth and accommodating 49 channels. The challenges of this design lie in selecting suitable values of τ and σ for 134 frequency points for which different sets of all the output parameters such as gain, input impedance (Z_in), front‐to‐back ratio (FTBR), first side lobe level (FSLL), voltage standing wave ratio (VSWR), and so forth are obtained and then averaged over to get Gain_av, Z_inAav, FTBR_av, FSLL_av, and VSWR_av close to the desired values. These average values are used to design suitable fitness function. Another important aspect of this article is to provide exhaustive design details for LPDA using network theory that would couple to the BFA for getting the optimized number of elements to satisfy the desired values of Z_inav, Gain_av, FTBR_av, FSLL_av, and VSWR_av, set as 50 Ω, 9 dBi, 40 dB, 40 dB, and 1.1, respectively. Moreover, this LPDA design considers the standard wire gauge dipole elements, which is just a very practical approach in the design procedure. © 2012 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2013.