58 research outputs found
On the equivalence of blind equalizers based on MRE and subspace intersections
No full textTwo classes of algorithms recently proposed for the blind equalization of multiple channels driven by a single source are the Mutually Referenced Equalizers (MRE) method by Gesbert et al., and the Subspace Intersection (SSI) method by van der Veen et al. Although these methods seem at first sight unrelated, we show here that a variant of the SSI method and a particular member in the class of MRE methods provide mathematically identical solutions
A theory of contracts for web services
No full text<p>Contracts are behavioural descriptions of Web services. We devise a theory of contracts that formalises the compatibility of a client to a service, and the safe replacement of a service with another service. The use of contracts statically ensures the successful completion of every possible interaction between compatible clients and services.</p>
<p>The technical device that underlies the theory is the definition of filters, which are explicit coercions that prevent some possible behaviours of services and, in doing so, they make services compatible with different usage scenarios. We show that filters can be seen as proofs of a sound and complete subcontracting deduction system which simultaneously refines and extends Hennessy's classical axiomatisation of the must testing preorder. The relation is decidable and the decision algorithm is obtained via a cut-elimination process that proves the coherence of subcontracting as a logical system.</p>
<p>Despite the richness of the technical development, the resulting approach is based on simple ideas and basic intuitions. Remarkably, its application is mostly independent of the language used to program the services or the clients. We also outline the possible practical impact of such a work and the perspectives of future research it opens.</p>
XQuery and Static Typing: Tackling the Problem of Backward Axes
No full textInternational audienceXQuery is a functional language dedicated to XML data querying and manipulation. As opposed to other W3C-standardized languages for XML (e.g. XSLT), it has been intended to feature strong static typing. Currently, however, some expressions of the language cannot be statically typed with any precision. We argue that this is due to a discrepancy between the semantics of the language and its type algebra: namely, the values of the language are (possibly inner) tree nodes, which may have siblings and ancestors in the data. The types on the other hand are regular tree types, as usual in the XML world: they describe sets of trees. The type associated to a node then corresponds to the subtree whose root is that node and contains no information about the rest of the data. This makes navigation expressions using `backward axes,' which return e.g. the siblings of a node, impossible to type. We discuss how to handle this discrepancy by improving the type system. We describe a logic-based language of extended types able to represent inner tree nodes and show how it can dramatically increase the precision of typing for navigation expressions. We describe how inclusion between these extended types and the classical regular tree types can be decided, allowing a hybrid system combining both type languages. The result is a net increase in precision of typing
A theory of contracts for web services
No full textContracts are behavioural descriptions of Web services. We devise a theory of contracts that formalises the compatibility of a client to a service, and the safe replacement of a service with another service. The use of contracts statically ensures the successful completion of every possible interaction between compatible clients and services. The technical device that underlies the theory is the definition of filters, which are explicit coercions that prevent some possible be-haviours of services and, in doing so, they make services compati-ble with different usage scenarios. We show that filters can be seen as proofs of a sound and complete subcontracting deduction system which simultaneously refines and extends Hennessy’s classical ax-iomatisation of the must testing preorder. The relation is decidable and the decision algorithm is obtained via a cut-elimination process that proves the coherence of subcontracting as a logical system. Despite the richness of the technical development, the resulting approach is based on simple ideas and basic intuitions. Remark-ably, its application is mostly independent of the language used to program the services or the clients. We also outline the possible practical impact of such a work and the perspectives of future re-search it opens. Categories and Subject Descriptors F.1.2 [Computation by Ab-stract Devices]: Modes of Computation—Parallelism and con
Étude de la formalisation des spécifications de bases de données géographiques en vue de leur intégration
No full textObjectif : faciliter l utilisation conjointe de plusieurs bases de données géographiques, et en particulier leur intégration dans un système de bases de données fédérées, grâce à une description homogène entre les différentes bases et autant que possible formelle de la sémantique précise des données, c est-à-dire des spécifications de contenu. Méthode : Les spécifications papier ont le défaut d être structurées conformément aux schémas des bases de données, qui sont hétérogènes et influencés par des choix d implémentation. Pour s affranchir de ce problème, on fait l hypothèse qu on peut trouver dans les spécifications un certain nombre de termes consensuels correspondant à des concepts géographiques partagés. Ces concepts formeraient ce qu on appelle une ontologie du domaine. L idée n est pas de créer cette ontologie de façon exhaustive mais de créer une ontologie partielle ad hoc, qu on étendra au fur et à mesure qu on rencontrera de nouveaux concepts dans les spécifications. Les spécifications sont alors représentées sous la forme de procédures de représentation qui à une entit géographique (instance d un concept donné) associent une ou plusieurs représentations dans les différentes bases, en fonction de la nature et des propriétés de l entité ; elles font donc le lien entre l ontologie et les schémas des différentes bases. Résultats : sur les thèmes hydrographie de la BDCarto et de la BDTopo, deux bases de données de l IGN, il semble que l hypothèse soit vérifiée (on arrive assez facilement à une ontologie commune). On a pu d autre part déterminer les principaux types de règles élémentaires nécessaires à la construction des procédures de représentation. Un langage formel dont la grammaire, définie en BNF, s appuie sur ces règles élémentaires a alors été proposé pour décrire les procédures de représentation. Enfin, un prototype logiciel muni d un parseur pour ce langage a été réalisé pour saisir, stocker et manipuler les spécifications formelleintegrating them into a federated database system, by describing the precise data meaning in a way both homogeneous between databases and as formal as possible. This precise data meaning is contained in the databases content specifications (surveying rules). Method : The general organization of the present specifications follows that of the databases schemata, but these schemas are heterogeneous and influenced by implementation problems. To overcome this problem, we suppose that it will be possible to find, in the specifications text, a number of common terms referring to shared geographical concepts. All these concepts would constitute what is called a domain ontology. Our idea is not to create a complete ontology but rather a partial, ad hoc one, which would be extended to take new concepts into account as needed. The specifications would then be represented as a bundle of what we call representation procedures, which describe how, given a geographic entity (instance of some geographical concept), one or more representations of this entity are built up into the different databases depending on the nature and the properties of the entity. Thus these procedures describe the links between the ontology and the schemata of the databases. Results : For the example of hydrography in two different IGN databases, BDCarto and BDTopo, our hypothesis seems confirmed : a common ontology could rather easily be defined. Concerning the representation procedures, we were able to establish the main kinds of elementary rules from which they can be constructed. To describe formally these procedures, we then defined a formal language whose grammar has been described in BNF and is based on these elementary rules. Finally, we have made a software prototype, containing a parser for this language, for entering, saving and handling the formal specificationsPARIS-EST Marne-la-Vallee-BU (774682101) / SudocSudocFranceF
Efficiently Deciding µ-calculus with Converse over Finite Trees
No full textInternational audienceWe present a sound and complete satisfiability-testing algorithm and its effective implementation for an alternation-free modal µ-calculus with converse, where formulas are cycle-free and are interpreted over finite ordered trees. The time complexity of the satisfiability-testing algorithm is 2^O(n) in terms of formula size n. The algorithm is implemented using symbolic techniques (BDD). We present crucial implementation techniques and heuristics that we used to make the algorithm as fast as possible in practice. Our implementation is available online, and can be used to solve logical formulas of significant size and practical value. We illustrate this in the setting of XML trees
On the Optimization of Recursive Relational Queries: Application to Graph Queries
No full textInternational audienceGraph databases have received a lot of attention as they are particularly useful in many applications such as social networks, life sciences and the semantic web. Various languages have emerged to query graph databases, many of which embed forms of recursion which reveal essential for navigating in graphs. The relational model has benefited from a huge body of research in the last half century and that is why many graph databases rely on techniques of relational query engines. Since its introduction, the relational model has seen various attempts to extend it with recursion and it is now possible to use recursion in several SQL or Datalog based database systems. The optimization of recursive queries remains, however, a challenge. We propose mu-RA, a variation of the Relational Algebra equipped with a fixpoint operator for expressing recursive relational queries. mu-RA can notably express unions of conjunctive regular path queries. Leveraging the fact that this fixpoint operator makes recursive terms more amenable to algebraic transformations, we propose new rewrite rules. These rules makes it possible to generate new query execution plans, that cannot be obtained with previous approaches. We present the syntax and semantics of mu-RA, and the rewriting rules that we specifically devised to tackle the optimization of recursive queries. We report on practical experiments that show that the newly generated plans can provide significant performance improvements for evaluating recursive queries over graphs
Parametric Polymorphism and Semantic Subtyping: the Logical Connection
No full textInternational audienceWe consider a type algebra equipped with recursive, product, function, intersection, union, and complement types together with type variables and implicit universal quantification over them. We consider the subtyping relation recently defined by Castagna and Xu over such type expressions and show how this relation can be decided in EXPTIME, answering an open question. The novelty, originality and strength of our solution reside in introducing a logical modeling for the semantic subtyping framework. We model semantic subtyping in a tree logic and use a satisfiability-testing algorithm in order to decide subtyping. We report on practical experiments made with a full implementation of the system. This provides a powerful polymorphic type system aiming at maintaining full static type-safety of functional programs that manipulate trees, even with higher-order functions, which is particularly useful in the context of XML.Nous considérons une algèbre de types comprenant des types récursifs, produits, fonctions, intersection, union et négation, ainsi que des variables de types soumises à une quantification universelle implicite. Nous considérons la relation de sous-typage définie récemment par Castagna et Xu sur cette algèbre de types et montrons que cette relation est décidable en EXPTIME, résolvant une question ouverte. La nouveauté, l'originalité et la force de notre solution résident dans l'introduction d'une modélisation logique du sous-typage sémantique. Nous représentons ce sous-typage dans une logique d'arbres et utilisons un algorithme de vérification de satisfaisabilité pour décider la relation. Nous présentons une implémentation complète du système et le résultat de plusieurs tests pratiques
- …
