Project WAM was closed in December 2012.
Project Tyrex was created as a follow-up.
Please refer to Tyrex to get the
latest information.
This page is no longer updated.
It is provided as historical background.
This list is also available as a single BibTeX file.
- XML Query-Update Independence Analysis
Revisited.
Muhammad Junedi, Pierre Genevès, Nabil Layaïda.
In Proceedings of the 2012 ACM Symposium on Document Engineering, pp. 95-98, ACM, September 2012. [bib, pdf, doi]XML transformations can be resource-costly in particular when applied to very large XML documents and document sets. Those transformations usually involve lots of XPath queries and may not need to be entirely re-executed following an update of the input document. In this context, a given query is said to be independent of a given update if, for any XML document, the results of the query are not affected by the update. We revisit Benedikt and Cheney’s framework for query-update independence analysis and show that performance can be drastically enhanced, contradicting his initial claims. The essence of our approach and results resides in the use of an appropriate logic, to which queries and updates are both succinctly translated. Compared to previous approaches, ours is more expressive from a theoretical point of view, equally accurate, and more efficient in practice. We illustrate this through practical experiments and comparative figures. - Toward Automated Schema-directed
Code Revision.
Raquel Oliveira, Pierre Genevès, Nabil Layaïda.
In Proceedings of the 2012 ACM Symposium on Document Engineering, pp. 103-106, ACM, September 2012. [bib, pdf, doi]Updating XQuery programs in accordance with a change of the input XML schema is known to be a time-consuming and error-prone task. We propose an automatic method aimed at helping developers realign the XQuery program with the new schema. First, we introduce a taxonomy of possible problems induced by a schema change. This allows to differentiate problems according to their severity levels, e.g. errors that require code revision, and semantic changes that should be brought to the developer’s attention. Second, we provide the necessary algorithms to detect such problems using a solver that checks satisfiability of XPath expressions. - SPARQL Query Containment Under SHI
Axioms.
Melisachew Chekol, Jérôme Euzenat, Pierre Genevès, Nabil Layaïda.
In Proceedings of the 26th AAAI Conference on Artificial Intelligence, pp. 10-16, AAAI Press, July 2012. [bib, pdf]SPARQL query containment under schema axioms is the problem of determining whether, for any RDF graph satisfying a given set of schema axioms, the answers to a query are contained in the answers of another query. This problem has major applications for verification and optimization of queries. In order to solve it, we rely on the μ-calculus. Firstly, we provide a mapping from RDF graphs into transition systems. Secondly, SPARQL queries and RDFS and SHI axioms are encoded into μ-calculus formulas. This allows us to reduce query containment and equivalence to satisfiability in the μ-calculus. Finally, we prove a double exponential upper bound for containment under SHI schema axioms. - A Lightweight Framework for
Authoring XML Multimedia Content on the Web.
Christine Vanoirbeek, Vincent Quint, Stéphane Sire, Cécile Roisin.
In Multimedia Tools and Applications (MTAP), Springer Netherlands, 2012. [bib, pdf, doi]This paper addresses the issue of authoring XML multimedia content on the web. It focuses on methods that apply to different kinds of contents, including structured documents, factual data, and multimedia objects. It argues in favor of a template-based approach that enhances the ability for multiple applications to use the produced content. This approach is illustrated by AXEL, an innovative multi-purpose client-side authoring framework intended for web users with limited skills. The versatility of the tool is illustrated through a series of use cases that demonstrate the flexibility of the approach for creating various kinds of web content. - SPARQL Query Containment under RDFS
Entailment Regime.
Melisachew Chekol, Jérôme Euzenat, Pierre Genevès, Nabil Layaïda.
In Proceedings of the 6th International Joint Conference on Automated Reasoning (IJCAR), pp. 134-148, Springer, June 2012. [bib, pdf]The problem of SPARQL query containment is defined as determining if the result of one query is included in the result of another for any RDF graph. Query containment is important in many areas, including information integration, query optimization, and reasoning about Entity-Relationship diagrams. We encode this problem into an expressive logic called μ-calculus: where RDF graphs become transition systems, queries and schema axioms become formulas. Thus, the containment problem is reduced to formula satisfiability test. Beyond the logic’s expressive power, satisfiability solvers are available for it. Hence, this study allows to exploit these advantages. - On the Analysis of Cascading Style
Sheets.
Pierre Genevès, Nabil Layaïda, Vincent Quint.
In Proceedings of the 21th international conference on World wide web, pp. 809-818, ACM, April 2012. [bib, pdf, doi]Developing and maintaining cascading style sheets (CSS) is an important issue to web developers as they suffer from the lack of rigorous methods. Most existing means rely on validators that check syntactic rules, and on runtime debuggers that check the behavior of a CSS style sheet on a particular document instance. However, the aim of most style sheets is to be applied to an entire set of documents, usually defined by some schema. To this end, a CSS style sheet is usually written w.r.t. a given schema. While usual debugging tools help reducing the number of bugs, they do not ultimately allow to prove properties over the whole set of documents to which the style sheet is intended to be applied. We propose a novel approach to fill this lack. We introduce ideas borrowed from the fields of logic and compile-time verification for the analysis of CSS style sheets. We present an original tool based on recent advances in tree logics. The tool is capable of statically detecting a wide range of errors (such as empty CSS selectors and semantically equivalent selectors), as well as proving properties related to sets of documents (such as coverage of styling information), in the presence or absence of schema information. This new tool can be used in addition to existing runtime debuggers to ensure a higher level of quality of CSS style sheets. - Le language audio pour mobiles
MAUDL et son moteur de rendu audio interactif IXE.
Yohan Lasorsa, Jacques Lemordant.
INRIA Report RR-7847, December 2011. [bib, html]Building a navigation system only based on audio guidance is a very complex task to carry out. You need to provide the user enough information to guide him without flooding him under an heavy load of sounds. Multiple kinds of guidance clues must be provided without overloading the auditive space. You also have to sort informations to give the user the most pertinent one at a given time. Finally, the system should be able to guide the user precisely in all kinds of environments. Based on these objectives, the Mobile Audio Language (MAUDL) has been defined in this research work, after a review of the limitations and problems existing with the current formats within a navigation context. Customization of the audio rendering is one aspect showcased by the usage of the different features available in MAUDL. In addition, a new sound manager named Interactive eXtensible Engine (IXE) has been developed to provide a software support to the language. It integrates all the current features of MAUDL and has been specifically designed for mobile platforms. This research report details the various problems encountered while developping such a system and the technical decisions that led to the conception of this library. - One Idea and Three Concepts for
Indoor-Outdoor Navigation.
Audrey Colbrant, Yohan Lasorsa, Jacques Lemordant, David Liodenot, Mathieu Razafimahazo.
INRIA Report RR-7849, December 2011. [bib, html]For pedestrian navigation when a precision of one step is required as for navigation of visually impaired people or if the envisaged mobile appplication needs to position POIs with a high precision, there is no real difference between indoor and outdoor navigation as an IMU-based localization system has to be used. IMU-based localization is not an absolute positioning system and proceeds by path integration so it must be associated to another kind of localization system such as GPS, WI-FI, RFID, IBR (Image-Based Recognition). Pedestrian navigation has to cope with the main difficulties encountered by visually impaired people, i.e. preplanning routes, recovery from unexpected detours and maintening heading. Path integration, 3D audio cues and structured environment are navigation aids used implicitly by visually impaired people and give them highly successful navigation. Our position is that a navigation system can be build starting from a conceptual definition of these three aids which are inter-related. Our prototype navigation system built above these three concepts, works indoor and outdoor when the environment is structured or has a regular layout. It’s a complex system with many services and data exchanges between concurrent processes. For this reason, we have build it using XML and Web technologies, allowing easy personnalization of the level of navigation aid, and easy authoring of personnal audio cues and POIs on a specific itinerary. - A Lightweight Framework for
Authoring XML Multimedia Content on the Web.
Christine Vanoirbeek, Vincent Quint, Stéphane Sire, Cécile Roisin.
INRIA Report RR-7848, December 2011. [bib, html]This report addresses the issue of authoring XML multimedia content on the web. It focuses on methods that apply to different kinds of contents, including structured documents, factual data, and multimedia objects. It argues in favor of a template-based approach that significantly enhances the ability for multiple applications to use the produced content. It presents AXEL, an innovative multipurpose client-side authoring framework targeted to web users with limited skills. The versatility of the tool is illustrated through a series of use cases that demonstrate the flexibility of the approach for creating various kinds of content. - On the Analysis of Cascading
Style Sheets.
Pierre Genevès, Nabil Layaïda, Vincent Quint.
INRIA Report RR-7808, November 2011. [bib, html]Developing and maintaining cascading style sheets (CSS) is an important issue to web developers as they suffer from the lack of rigorous methods. Most existing means rely on validators that check syntactic rules, and on runtime debuggers that check the behavior of a CSS style sheet on a particular document instance. However, the aim of most style sheets is to be applied to an entire set of documents, usually defined by some schema. To this end, a CSS style sheet is usually written w.r.t. a given schema. While usual debugging tools help reducing the number of bugs, they do not ultimately allow to prove properties over the whole set of documents to which the style sheet is intended to be applied. We propose a novel approach to fill this lack. We introduce ideas borrowed from the fields of logic and compile-time verification for the analysis of CSS style sheets. We present an original tool based on recent advances in tree logics. The tool is capable of statically detecting a wide range of errors (such as empty CSS selectors and semantically equivalent selectors), as well as proving properties related to sets of documents (such as coverage of styling information), in the presence or absence of schema information. This new tool can be used in addition to existing runtime debuggers to ensure a higher level of quality of CSS style sheets. - Parametric Polymorphism and Semantic
Subtyping: the Logical Connection.
Nils Gesbert, Pierre Genevès, Nabil Layaïda.
In ICFP’11, Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming, pp. 107-116, ACM, September 2011. [bib, pdf, doi]We consider a type algebra equipped with recursive, product, function, intersection, union, and complement types together with type variables and universal quantification over them. We define the subtyping relation between such type expressions, and prove its decidability. This solves an open problem that has recently attracted a considerable research effort. 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 show how the subtyping relation can be decided in EXPTIME. 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. - PSPARQL Query Containment.
Melisachew Chekol, Jérôme Euzenat, Pierre Genevès, Nabil Layaïda.
In DBPL 2011, Proceedings of the 13th International Symposium on Database Programming Languages, August 2011. [bib, pdf]Querying the semantic web is mainly done through SPARQL. This language has been studied from different perspectives such as optimization and extension. One of its extensions, PSPARQL (Path SPARQL) provides queries with paths of arbitrary length. We study the static analysis of queries written in this language, in particular, containment of queries: determining whether, for any graph, the answers to a query are contained in those of another query. Our approach consists in encoding RDF graphs as transition systems and queries as μ-calculus formulas and then reducing the containment problem to testing satisfiability in the logic. - Query reasoning on trees with types,
interleaving and counting.
Everardo Bárcenas, Pierre Genevès, Nabil Layaïda, Alan Schmitt.
In Proceedings of the 22nd International Joint Conference on Artificial Intelligence IJCAI’2011, vol. 2, pp. 718-723, AAAI Press, July 2011. [bib, html]A major challenge of query language design is the combination of expressivity with effective static analyses such as query containment. In the setting of XML, documents are seen as finite trees, whose structure may additionally be constrained by type constraints such as those described by an XML schema. We consider the problem of query containment in the presence of type constraints for a class of regular path queries extended with counting and interleaving operators. The counting operator restricts the number of occurrences of children nodes satisfying a given logical property. The interleaving operator provides a succinct notation for describing the absence of order between nodes satisfying a logical property. We provide a logic-based framework supporting these operators, which can be used to solve common query reasoning problems such as satisfiability and containment of queries in exponential time. - Enhancing an XML Publishing
Workflow for Web Multimedia.
Cécile Roisin, Fabien Cazenave, Vincent Quint, Ludovic Gaillard, Dominique Saint-Martin.
INRIA Report RR-7836, July 2011. [bib, html]A challenge for the C2M project is to develop a document workflow for authoring and producing web multimedia documents with a special attention for the aesthetic quality of the final rendering. In this paper we discuss the requirements for advanced multimedia authoring services from a document engineering point of view. Our approach consists in providing a post-editing service to allow authors to adjust their multimedia presentation directly on the final form of the document. The first step of the proposal is to provide a web rendering en- gine based on the latest advances in web standards. For that purpose, we have developed timesheets.js, a JavaScript library for publishing multimedia web documents. It takes advan- tage of the new features of the HTML5 and CSS3 web standards and enables synchronization of multimedia contents. The second step consists in designing web-aware authoring tools based on this library, thus providing authors with direct editing services for producing high quality multimedia documents. - Impact of XML Schema Evolution.
Pierre Genevès, Nabil Layaïda, Vincent Quint.
In ACM Transactions on Internet Technology (TOIT), vol. 11 (1), pp. 4-1, ACM, July 2011. [bib, html, doi]We consider the problem of XML Schema evolution. In the ever-changing context of the web, XML schemas continuously change in order to cope with the natural evolution of entities they describe. Schema changes have important consequences. First, existing documents valid with respect to the original schema are no longer guaranteed to fulfill the constraints described by the evolved schema. Second, the evolution also impacts programs manipulating documents whose structure is described by the original schema. We propose a unifying framework for determining the effects of XML Schema evolution both on the validity of documents and on queries. The system is very powerful in analyzing various scenarios in which forward/backward compatibility of schemas is broken, and in which the result of a query may not be anymore what was expected. Specifically, the system offers a predicate language which allows one to formulate properties related to schema evolution. The system then relies on exact reasoning techniques to perform a fine-grained analysis. This yields either a formal proof of the property or a counter-example that can be used for debugging purposes. The system has been fully implemented and tested with real-world use cases, in particular with the main standard document formats used on the web, as defined by W3C. The system identifies precisely compatibility relations between document formats. In case these relations do not hold, the system can identify queries that must be reformulated in order to produce the expected results across successive schema versions. - Inconsistent Path Detection for XML
IDEs.
Pierre Genevès, Nabil Layaïda.
In Proceedings of the 33rd International Conference on Software Engineering, ICSE 2011, pp. 983-985, ACM, May 2011. [bib, html, doi]We present the first IDE augmented with static detection of inconsistent paths for simplifying the development and debugging of any application involving XPath expressions. - Mixed Reality Browsers.
Jacques Lemordant.
In International workshop on AR Standards, February 2011. [bib, pdf]This paper focuses on Mixed Reality Browsers (MRB) that merge real and virtual worlds somewhere along the virtuality continuum which connects completely real environments to completely virtual ones. We present the audio-visual MRB developed by the WAM project-team of INRIA at Grenoble, which uses a RDF data format for POIs whose URIs refer to content expressed in HTML5 and in a declarartive data format for interactive audio. - Automated reasoning on trees
with cardinality constraints.
Everardo Bárcenas-Patiño.
Ph.D. thesis, Institut National Polytechnique de Grenoble, February 2011. [bib, html]Arithmetical constraints are widely used in formal languages like regular expressions, tree grammars and paths. In XML they are used to impose bounds on the number of occurrences described by content models of schema languages (XML Schema, RelaxNG). In query languages (XPath, XQuery), they allow selecting nodes that have a bounded number of nodes reachable by a given path expression. Counting types and paths are thus natural extensions of their countless counterparts already regarded as the core constructs in XML languages and type systems. One of the biggest challenges in XML is to develop automated techniques for ensuring static-type safety and optimization techniques. To this end, there is a need to solve some basic reasoning tasks that involve constructions such as counting XML schemas and XPath expressions. Every compiler of XML programs will have to routinely solve problems such as type and path type- checking, for ensuring at compile time that invalid documents can never arise as the output of XML processing code. This thesis studies efficient reasoning frameworks able to express counting constraints on tree structures. It was recently shown that the μ-calculus, when extended with counting constraints on immediate successor nodes is undecid able over graphs. Here we show that, when interpreted over finite trees, the logic with counting constraints is decidable in single exponential time. Furthermore, this logic allows more general counting operators. For example, the logic can pose numerical constraints on number of ancestors or descendants. We also present linear translations of counting XPath expressions and XML schemas into the logic. - Instrumentation des interrogations
orales Support multimédia à l’évaluation et à la capitalisation des
interrogations orales.
Jan Mikác, Cécile Roisin, Jean-Marc Wolff.
In TICE2010 : 7ème Colloque Technologies de l’Information et de la Communication pour l’Enseignement, December 2010. [bib, pdf]In this paper we propose an authoring service dedicated to the support of annotating and sharing oral examinations. Basically it allows: (1) authoring live text annotations while the student oral presentation is recorded as an audio media; (2) possibly editing the annotated audio for adding annotations and adjusting their synchronization with the audio track; and (3) generating a multimedia document in a standard format to enable its publication on multimedia platforms. The paper describes the results of the first experimentations of this tool. - From Templates to Schemas: Bridging the
Gap Between Free Editing and Safe Data Processing.
Vincent Quint, Cécile Roisin, Stéphane Sire, Christine Vanoirbeek.
In DocEng 2010: Proceedings of the Tenth ACM Symposium on Document Engineering, pp. 61-64, ACM, September 2010. [bib, pdf, doi]In this paper we present tools that provide an easy way to edit XML content directly on the web, with the usual benefit of valid XML content. These tools make it possible to create content targeted for lightweight web applications. Our approach uses (1) the XTiger template language, (2) the AXEL Javascript library for authoring structured XML content and (3) XSLT transformations for generating XML schemas against which the XML content can be validated. Template-driven editing allows any web user to easily enter content while schemas make sure applications can safely process this content. - A Low-Cost Global Network for Data
Collection and Query.
Audrey Colbrant, Jacques Lemordant, Phuntsok Dorjee.
In Proceedings of the 2nd Extreme Workshop on Communication, ExtremeCom 2010, ACM, September 2010. [bib, pdf]We present two complementary research ideas and a prototype framework based on these ideas. The first idea is that by using semantic URIs, Xquery and XML Data Models, HTTP Responses with embedded URIs, it should be possible to construct easily rich web services over SMS for data collection and query. The second idea is that by using several mobile SMS-Web gateways, we can build a low-cost global network with these rich web services. Hospitals in India, including Delek Hospital of Dharamsala, are using the DOTS protocol of the World Health Organisation to fight tuberculosis in Tibetan settlements located in India and Nepal. Our prototype framework implements this protocol. - Sound Objects for SVG.
Audrey Colbrant, Yohan Lasorsa, Jacques Lemordant, David Liodenot, Mathieu Razafimahazo.
In Proceedings of SVG Open 2010, August 2010. [bib, pdf]A sound object can be defined as a time structure of audio chunks whose duration is on the time scale of 100 ms to several seconds. Sound objects have heterogeneous and time-varying properties. They are the basic elements of any format for Interactive Audio (IA). We have designed an XML language, A2ML, for Interactive Audio which offers, concerning the sequencing of sounds, a level of capabilities similar to that of iXMF, the interactive audio file format defined by the Interactive Audio Special Interest Group (IASIG). A2ML uses SMIL timing attributes to control the synchronization of sound objects and supports 3D sound rendering, DSP and positional parameters’s animation, by embedding the SMIL animation module. Like in a traditional mixing console, mix groups can be used to regroup multiple sound objects and apply mix parameters to all of them at the same time. An API allows external control and dynamic instantiation of sound objects. As with graphics, a declarative language for interactive audio is much more powerful than a node-graph based approach implemented using an imperative language. The structured declarative model offers easier reuse, transformability, accessibility, interoperability and authoring. An XML declarative language for audio like A2ML could help to reach the goal of the IXMF workgroup, i.e. build a system by which composers and sound designers create an interactive soundtrack and audition it by simulating target application control input while working in the authoring environment. In this paper, we will show how an XML language for interactive audio can be used with SVG. After an introduction to the history of sound objects, we will use the example of a computational character with a simple orient behaviour to demonstrate the complementarity of SVG and A2ML. The best way to use these two languages is to synchronize them with a third one, a tag-value dispatching language. We will then present a complex application for which the use of both SVG and A2ML is natural, i.e. a navigation system for visually impaired people based on OpenStreetMap. - Basic Concepts in Augmented Reality
Audio.
Jacques Lemordant.
In W3C Workshop: Augmented Reality on the Web, June 2010. [bib, pdf]The basic difference between real and virtual sound environments is that virtual sounds are originating from another environment or are artificially created, whereas the real sounds are the natural existing sounds in the user’s own environment. Augmented Reality Audio combines these aspects in a way where real and virtual sound scenes are mixed so that virtual sounds are perceived as an extension or a complement to the natural ones. - Semantic Adaptation of Multimedia
Documents.
Sébastien Laborie, Jérôme Euzenat, Nabil Layaïda.
In Multimedia Tools and Applications (MTAP), vol. 55 (3), pp. 379-398, Springer Netherlands, June 2010. [bib, html, doi]Multimedia documents have to be played on multiple device types. Hence, usage and platform diversity requires document adaptation according to execution contexts, not generally predictable at design time. In an earlier work, a semantic framework for multimedia document adaptation was proposed. In this framework, a multimedia document is interpreted as a set of potential executions corresponding to the author specification. To each target device corresponds a set of possible executions complying with the device constraints. In this context, adapting requires to select an execution that satisfies the target device constraints and which is as close as possible from the initial composition. This theoretical adaptation framework does not specifically consider the main multimedia document dimensions, i.e., temporal, spatial and hypermedia. In this paper, we propose a concrete application of this framework on standard multimedia documents. For that purpose, we first define an abstract structure that captures the spatio-temporal and hypermedia dimensions of multimedia documents, and we develop an adaptation algorithm which transforms in a minimal way such a structure according to device constraints. Then, we show how this can be used for adapting concrete multimedia documents in SMIL through converting the documents in the abstract structure, using the adaptation algorithm, and converting it back in SMIL. This can be used for other document formats without modifying the adaptation algorithm. - Eliminating Dead-Code from XQuery
Programs.
Pierre Genevès, Nabil Layaïda.
In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering, ICSE 2010, pp. 305-306, ACM, May 2010. [bib, pdf, doi]One of the challenges in web software development is to help achieving a good level of quality in terms of code size and runtime performance, for increasingly popular domain spe- cific languages such as XQuery. We present an IDE equipped with static analysis features for assisting the programmer. These features are capable of identifying and eliminating dead code automatically. The tool is based on newly devel- oped formal programming language verification techniques, which are now mature enough to be introduced in the process of software development. - Augmented Reality Audio Editing.
Jacques Lemordant, Yohan Lasorsa.
In 128th AES Convention, May 2010. [bib, pdf]The concept of augmented reality audio (ARA) characterizes techniques where a physically real sound and voice environment is extended with virtual, geolocalized sound objects. We show that the authoring of an ARA scene can be done through an iterative process composed of two stages: in the first one the author has to move in the rendering zone to apprehend the audio spatialization and the chronology of the audio events and in the second one a textual editing of the sequencing of the sound sources and DSP acoustics parameters is done. This authoring process is based on the join use of two XML languages, OpenStreetMap for maps and A2ML for Interactive 3D Audio. A2ML being a format for a cue-oriented interactive audio system, requests for interactive audio services are done through TCDL, a Tag-based Cue Dispatching language. This separation of modeling and audio rendering is similar to what is done for the web of documents with HTML and CSS style sheets. - Debugging Standard Document Formats.
Nabil Layaïda, Pierre Genevès.
In Proceedings of the 19th International Conference on World Wide Web (WWW 2010), pp. 1269-1272, ACM, April 2010. [bib, pdf, doi]We present a tool for helping XML schema designers to obtain a high quality level for their specifications. The tool allows one to analyze relations between classes of XML documents and formally prove them. For instance, the tool can be used to check forward and backward compatibilities of recommendations. When such a relation does not hold, the tool allows one to identify the reasons and reports detailed counter-examples that exemplify the problem. For this purpose, the tool relies on recent advances in logic-based automated theorem proving techniques that allow for efficient reasoning on very large sets of XML documents. We believe this tool can be of great value for standardization bodies that define specifications using various XML type definition languages (such as W3C specifications), and are concerned with quality assurance for their normative recommendations. - On the Count of Trees.
Everardo Bárcenas, Pierre Genevès, Nabil Layaïda, Alan Schmitt.
INRIA Report 7251, August 2010. [bib, html]Regular tree grammars and regular path expressions constitute core constructs widely used in programming languages and type systems. Nevertheless, there has been little research so far on frameworks for reasoning about path expressions where node cardinality constraints occur along a path in a tree. We present a logic capable of expressing deep counting along paths which may include arbitrary recursive forward and backward navigation. The counting extensions can be seen as a generalization of graded modalities that count immediate successor nodes. While the combination of graded modalities, nominals, and inverse modalities yields undecidable logics over graphs, we show that these features can be combined in a decidable tree logic whose main features can be decided in exponential time. Our logic being closed under negation, it may be used to decide typical problems on XPath queries such as satisfiability, type checking with relation to regular types, containment, or equivalence. - Authoring XML all the Time, Everywhere
and by Everyone.
Stéphane Sire, Christine Vanoirbeek, Vincent Quint, Cécile Roisin.
In Proceedings of XML Prague 2010, pp. 125-149, Institute for Theoretical Computer Science, March 2010. [bib, pdf]This article presents a framework for editing, publishing and sharing XML content directly from within the browser. It comes in two parts: XTiger XML and AXEL. XTiger XML is a document template specification language for creating document models. AXEL is a client-side Javascript library that turns the document template into a document editing application running in the browser. This framework is targeted at non XML speaking end users, since it preserves end users from XML syntax during editing. Its current implementation proposes a pseudo-WYSIWYG user interface where the document template provides a document-oriented editing metaphor, or a more form-oriented metaphor, depending on the template. - XML Reasoning Made Practical.
Pierre Genevès, Nabil Layaïda.
In Proceedings of the 26th IEEE International Conference on Data Engineering, ICDE 2010, pp. 1169-1172, IEEE, March 2010. [bib, pdf]We present a tool for the static analysis of XPath queries and XML Schemas. The tool introduces techniques used in the field of verification (such as binary decision diagrams) in order to efficiently solve XPath query satisfiability, containment, and equivalence, in the presence of real-world XML Schemas. The tool can be used in query optimizers, in order to prove soundness of query rewriting. It can also be used in type-checkers and optimizing compilers that need to perform all kinds of compile-time analyses involving XPath queries and XML tree constraints. - Semantic Multimedia Document
Adaptation with Functional Annotations.
Sébastien Laborie, Jérôme Euzenat, Nabil Layaïda.
In Proceedings of the 4th International Workshop on Semantic Media Adaptation and Personalization, SMAP’09, pp. 44-49, IEEE Computer Society, December 2009. [bib, pdf, doi]The diversity of presentation contexts for multimedia documents requires the adaptation of document specifications. In an earlier work, we have proposed a semantic adaptation framework for multimedia documents. This framework captures the semantics of the document composition and transforms the relations between multimedia objects according to adaptation constraints. In this paper, we show that relying on document composition alone for adaptation restricts the set of relevant candidate solutions and may even divert the adaptation from the authors intent. Hence, we propose to introduce functional annotations to guide the adaptation process. Theses annotations allow to refine the role of multimedia objects in the document. We show that SMIL documents could embed functional annotations encoded in RDF. These multimedia documents are then adapted thanks to an interactive adaptation tool. - An Interactive Audio System for
Mobiles.
Yohan Lasorsa, Jacques Lemordant.
In 127th AES Convention, Audio Engineering Society, October 2009. [bib, pdf]This paper presents an XML format for embedded interactive audio deriving from well-established formats like iXMF and SMIL. We introduce in this format a new paradigm for audio elements and animations synchronization, using a flexible event-driven system in conjunction with graph description capabilities to replace audio scripting. The concepts of this new format are explained through the building of a virtual interactive jungle environment. Then we have implemented a sound manager for J2ME smartphones and the iPhone. Guidance applications for blind people based on this audio system are being developed. - On the Analysis of Queries with
Counting Constraints.
Everardo Bárcenas, Pierre Genevès, Nabil Layaïda.
In DocEng’09: Proceedings of the Ninth ACM Symposium on Document Engineering, pp. 21-24, ACM, September 2009. [bib, pdf, doi]We study the analysis problem of XPath expressions with counting constraints. Such expressions are commonly used in document transformations or programs in which they select portions of documents subject to transformations. We explore how recent results on the static analysis of navigational aspects of XPath can be extended to counting constraints. The static analysis of this combined XPath fragment allows to detect bugs in transformations and to perform many kinds of optimizations of document transformations. More precisely, we study how a logic for finite trees capable of expressing upward and downward recursive navigation, can be equipped with a counting operator along regular path expressions. - Identifying Query Incompatibilities
with Evolving XML Schemas.
Pierre Genevès, Nabil Layaïda, Vincent Quint.
In ICFP’09, Proceedings of the 2009 ACM SIGPLAN International Conference on Functional Programming, pp. 221-230, August 2009. [bib, pdf, doi]During the life cycle of an XML application, both schemas and queries may change from one version to another. Schema evolutions may affect query results and potentially the validity of produced data. Nowadays, a challenge is to assess and accommodate the impact of these changes in evolving XML applications. Such questions arise naturally in XML static analyzers. These analyzers often rely on decision procedures such as inclusion between XML schemas, query containment and satisfiability. However, existing decision procedures cannot be used directly in this context. The reason is that they are unable to distinguish information related to the evolution from information corresponding to bugs. This paper proposes a predicate language within a logical framework that can be used to make this distinction. We present a system for monitoring the effect of schema evolutions on the set of admissible documents and on the results of queries. The system is very powerful in analyzing various scenarios where the result of a query may not be anymore what was expected. Specifically, the system is based on a set of predicates which allow a fine-grained analysis for a wide range of forward and backward compatibility issues. Moreover, the system can produce counterexamples and witness documents which are useful for debugging purposes. The current implementation has been tested with realistic use cases, where it allows identifying queries that must be reformulated in order to produce the expected results across successive schema versions. - Analysis of Haptics Evolution from
Web Search Engines’ Data.
Agnès Guerraz, Céline Loscos.
In Journal of Multimedia (JMM), vol. 4 (4), pp. 196-203, Academy Publisher, August 2009. [bib, pdf]This article proposes using search engine results data such as the number of results containing relevant terms, to measure the evolution of Haptics, the field devoted to the science and technology of the sense of touch. Haptics is a complex discipline which is at the intersection of the knowledge of several specialized fields like robotics, computer science, psychology, and mathematics. It can also appear as a new and emergent discipline due to the fact that many promising haptic interfaces, which allow innovative multi- modal applications in many fields, have become mature only recently. The study presented in this article uses data collected at different periods of time (in December 1999, January 2004, January 2005, November 2006 and April 2007) on Web search engines from requests on three different terminologies: haptique, haptik and haptics, taken respectively from French, German, and English languages. The evolution of Haptics is seemingly reflected by to the online frequency of these specific terms over time. This evolution has been measured by considering the Internet community through search engines such as Google or Yahoo!. - Réifier et réutiliser les pratiques
d’enseignement : développement participatif d’un scénario et de
services pour les communautés de pratique.
Bernadette Charlier, Aida Boukottaya, Amaury Daele, France Henri, Cécile Roisin, Annick Rossier-Morel.
In EIAH 09, pp. 223-230, INRP Lyon, June 2009. [bib, pdf]Cet article décrit et évalue un scénario de réification et de réutilisation de pratiques professionnelles ainsi que les services interopérables supportant le scénario développés en appliquant une méthode de design participatif. Après avoir présenté le contexte de la recherche et décrit la méthode de design participatif appliquée et ses principaux instruments, le scénario de réification, et les services développés sont tout d’abord présentés et ensuite évalués dans le cadre d’une communauté d’enseignant-e-s de l’enseignement supérieur. En conclusion, des pistes de développement sont proposées tant au niveau des supports aux apprentissages que des solutions technologiques. Enfin, un retour critique est proposé sur la méthode de design participatif, ses conditions de mise en oeuvre et ses résultats. - Counting in Trees along
Multidirectional Regular Paths.
Everardo Bárcenas, Pierre Genevès, Nabil Layaïda.
In PLAN-X’09, Proceedings of the ACM SIGPLAN Workshop on Programming Language Techniques for XML, January 2009. [bib, html]We propose a tree logic capable of expressing simple cardinality constraints on the number of nodes selected by an arbitrarily deep regular path with backward navigation. Specifically, a sublogic of the alternation-free μ-calculus with converse for finite trees is extended with a counting operator in order to reason on the cardinality of node sets. Also, we developed a bottom-up tableau-based satisfiability-checking algorithm, which resulted to have the same complexity than the logic without the counting operator: a simple exponential in the size of a formula. - XML Reasoning Solver User
Manual.
Pierre Genevès, Nabil Layaïda.
INRIA Report 6726, November 2008. [bib]This manual provides documentation for using the logical solver - Ensuring Query Compatibility
with Evolving XML Schemas.
Pierre Genevès, Nabil Layaïda, Vincent Quint.
INRIA Report 6711, November 2008. [bib, pdf]During the life cycle of an XML application, both schemas and queries may change from one version to another. Schema evolutions may affect query results and potentially the validity of produced data. Nowadays, a challenge is to assess and accommodate the impact of theses changes in rapidly evolving XML applications. This article proposes a logical framework and tool for verifying forward/backward compatibility issues involving schemas and queries. First, it allows analyzing relations between schemas. Second, it allows XML designers to identify queries that must be reformulated in order to produce the expected results across successive schema versions. Third, it allows examining more precisely the impact of schema changes over queries, therefore facilitating their reformulation. - Comment bâtir un cours multimédia
avec LimSee3 ?.
Jan Mikác, Cécile Roisin.
EPI Report, October 2008. [bib, pdf]Nous présentons le logiciel d’édition multimédia LimSee3 : après une revue du paysage actuel des outils d’édition pour le multimédia et de la place que LimSee3 y occupe, nous déroulons un exemple d’utilisation détaillé dans le domaine de l’enseignement, en insistant notamment sur l’utilisation des modèles de documents, la simplicité des gestes de base et la possibilité d’édition plus poussée. Nous concluons en revenant sur les points forts du logiciel par rapport aux outils existants. - An Export Architecture for a
Multimedia Authoring Environment.
Jan Mikác, Cécile Roisin, Bao Duc.
In DocEng’08: Proceedings of the eigth ACM Symposium on Document Engineering, pp. 28-31, ACM, September 2008. [bib, pdf, doi]In this paper, we propose an export architecture that provides a clear separation of multimedia authoring services from publication services. We illustrate this architecture with the LimSee3 authoring tool and several standard publication formats: Timesheets, SMIL, and XHTML. - Efficient Static Analysis of
XML Paths and Types.
Pierre Genevès, Nabil Layaïda, Alan Schmitt.
INRIA Report 6590, July 2008. [bib, pdf]We present an algorithm to solve XPath decision problems under regular tree type constraints and show its use to statically type-check XPath queries. To this end, we prove the decidability of a logic with converse for finite ordered trees whose time complexity is a simple exponential of the size of a formula. The logic corresponds to the alternation free modal μ-calculus without greatest fixpoint, restricted to finite trees, and where formulas are cycle-free. Our proof method is based on two auxiliary results. First, XML regular tree types and XPath expressions have a linear translation to cycle-free formulas. Second, the least and greatest fixpoints are equivalent for finite trees, hence the logic is closed under negation. Building on these results, we describe a practical, effective system for solving the satisfiability of a formula. The system has been experimented with some decision problems such as XPath emptiness, containment, overlap, and coverage, with or without type constraints. The benefit of the approach is that our system can be effectively used in static analyzers for programming languages manipulating both XPath expressions and XML type annotations (as input and output types). - Adaptation spatio-temporelle et
hypermédia de documents multimédia.
Sébastien Laborie, Jérôme Euzenat, Nabil Layaïda.
In Atelier Représentation et Raisonnement sur le Temps et l’Espace (RTE), pp. 1-13, Hermès, June 2008. [bib, pdf]Currently, multimedia documents may have to be executed on multiple devices such as mobile phones, PDAs, desktop computers, set-top boxes, etc. Hence, usage and platform diversity requires document adaptation according to execution contexts, sometimes unpredictable at design time. We propose to abstract from format specific details by defining a structure which expresses a set of objects and the relations between them. In order to capture the spatio-temporal and hypermedia dimensions of the document, we point out in this paper that these objects are multimedia objects and hypermedia links, and that relations between them are spatio-temporal. In this context, adapting amounts to modify in a minimal way the document abstraction according to the target device constraints. In order to show the applicability of our framework, we implement a prototype which adapts SMIL documents. - Adaptation sémantique de
documents multimédia.
Sébastien Laborie.
Ph.D. thesis, Université Joseph Fourier, Grenoble, May 2008. [bib, html]Un document multimédia marie les technologies de l’écrit, de l’image et du son. Actuellement, les documents multimédia doivent pouvoir être exécutés sur de nombreuses plates-formes (téléphones portables, PDA, ordinateurs de bureau, lecteurs de salon...). Cette diversification des utilisations et des supports nécessite l’adaptation des documents à leur contexte d’exécution, parfois imprévisible au moment de la conception du document. Pour s’affranchir des langages ou formats de description multimédia, nous abstrayons les documents en une structure exprimant l’ensemble des relations entre objets du document. Les relations entre objets sont d’ordre temporel, spatial, hypermédia voire inter-dimensionnel, et peuvent être de nature qualitative. Cette structure capture la sémantique des documents car elle est capable de couvrir chacune de ses exécutions potentielles. Dans ce contexte, adapter va consister à calculer un ensemble d’exécutions le plus proche possible de ces exécutions potentielles qui satisfont les contraintes d’adaptation imposées par une plate-forme cible. À cet effet, les relations de la structure abstraite sont modifiées de sorte de satisfaire ces contraintes d’adaptation. Nous montrons, pour chaque dimension du document, comment réaliser ceci de manière réaliste. Afin de montrer l’applicabilité d’une telle approche, nous la développons dans un cadre adapté au standard SMIL pour lequel nous déclinons les adaptations spatiales, temporelles, spatio-temporelles et hypermédia. Nous sommes amenés à développer des techniques spécifiques pour les représentations spatiales et temporelles efficaces. Nous explorons aussi des approches impliquant la suppression d’objets. - Static Analysis of XML Programs.
Pierre Genevès, Nabil Layaïda.
In ERCIM News, pp. 33-34, January 2008. [bib, html]Static analysers for programs that manipulate Extensible Markup Language (XML) data have been successfully designed and implemented based on a new tree logic by the WAM (Web, Adaptation and Multimedia) research team, a joint lab of INRIA and Laboratoire d’Informatique de Grenoble. This is capable of handling XML Path Language (XPath) and XML types such as Document Type Definitions (DTDs) and XML Schemas. - Modèle d’édition de document
multimédia.
Duc Le.
Masters thesis, Institut de la Francophonie pour l’Informatique, Hanoï, October 2007. [bib, html]Les travaux de ce stage consistent à étudier les techniques d’édition de document multimédia, le modèle d’édition de LimSee3, les propositions et les expérimentations d’exportation de document LimSee3 vers les formats de présentation multimédia. Nous présentons les différents modèles d’édition qui sont employés par les outils existants. En plus, nous examinons d’exportation de document LimSee3 vers le format de document multimédia comme SMIL et le format qui ne supporte pas directement d’expression temporelle comme XHTML. En fait, le processus d’exportation est complexe en raison de la diversité de format de présentation de document multimédia. Nous proposons deux approches d’exportation ; l’un utilise Java et l’autre utilise un format intermédiaire avec les feuilles XSL. Le résultat est un cadre d’application offert au service d’exportation et les exportateurs de document LimSee3 vers de formats SMIL, XHTML+CSS+JavaScript, et un ordonnanceur en JavaScript qui permet de rajouter les scénarios temporels aux documents XHTML. - Deciding XPath Containment with MSO.
Pierre Genevès, Nabil Layaïda.
In Data and Knowledge Engineering (DKE), vol. 63 (1), pp. 108-136, October 2007. [bib, html]XPath is the standard language for addressing parts of an XML document. We present a sound and complete decision procedure for containment of XPath queries. The considered XPath fragment covers most of the language features used in practice. Specifically, we show how XPath queries can be translated into equivalent formulas in monadic second-order logic. Using this translation, we construct an optimized logical formulation of the containment problem, which is decided using tree automata. When the containment relation does not hold between two XPath expressions, a counter-example XML tree is generated. We provide practical experiments that illustrate the efficiency of the decision procedure for realistic scenarios. - Indeterminate Adaptive Digital
Audio for Games on Mobiles.
Jacques Lemordant, Agnès Guerraz.
In From Pac-Man to Pop Music, editors: Karen Collins. Ashgate, 2007. [bib, html]A mobile game is a video game played on a mobile phone. The game market for mobiles is clearly regarded as a market with a future, as the multiple investments carried out by the large world editors on this segment testify. The mobiles are true platforms of large and general public games: mobile games can be downloaded via the mobile operator’s radio network, WLAN, bluetooth or USB connection. Mobiles phones give game developers a unique set of tools and behaviours and with a little creativity, game developers can make some really great games for this platform. The challenges posed by portable devices are numerous, but the biggest complaint of many in the industry is the lack of standards. It is necessary to adapt each game to the various models of existing terminals, which do not offer the same features (memory, processing power, keys...). Consequently, the number of different versions of a game rises to several hundreds. As we will see, Java Micro Edition (J2ME) attempts with some success to solve these problems. - Mobile Immersive Music.
Jacques Lemordant, Agnès Guerraz.
In Proceedings of the 2007 International Computer Music Conference, ICMC 07, pp. 21-24, ICMA, San Francisco, August 2007. [bib, html]Due to obvious portability constraints, mobile technology excludes large electronic displays for visual immersion. On the contrary, sound heard over headphones is ideally suited for mobile applications. The use of stereo headphones or stereo speakers on mobile devices enables to take advantage of binaural technology which can provide an immersive sound experience for a variety of applications ranging from stereo widening of music (creating an out of the head listening experience) to full 3-D positional audio. Advances in audio are going to help bring in richer multimedia, increase quality of mobile music and help create more interactive and immersive audio applications. Interaction with sound in 3D audio space is no more limited to indoor environment [8]. In this paper, we report on an architecture for multimedia applications on mobile devices separating content creation (audio and graphics) from content manipulation. We have developed a markup format for interactive and spatialized audio on mobiles which can be used an interface between the sound designer and the application programmer. After presenting an overview of the key concepts in designing a format for interactive and spatialized audio and the methodology used to build the corresponding sound API , we describe its use in a mobile immersive music application for Copenhagen Channels where interactivity with the music is done through GPS waypoints. - Editing with Style.
Vincent Quint, Irène Vatton.
In Proceedings of the 2007 ACM Symposium on Document Engineering, DocEng 2007, pp. 151-160, ACM Press, August 2007. [bib, html]HTML has popularized the use of style sheets, and the advent of XML has stressed the importance of style as a key area complementing document structure and content. A number of tools are now available for producing HTML and XML documents, but very few are addressing style issues. In this paper we analyze the requirements for style manipulation tools, based on the main features of the CSS language. We discuss methods and techniques that meet these requirements and that can be used to efficiently support web authors in style sheet manipulation. The discussion is illustrated by the recent developments made in the Amaya web authoring environment. - Un système expert d’aide à la
classification taxonomique de classes de descripteurs.
Marc Caillet.
In IC 2007, July 2007. [bib, html]Dans le cadre de la valorisation du patrimoine audiovisuel, nous nous intéressons à l’ingénierie d’applications multimédias qui reposent sur des descripteurs de documents audiovisuels. Ces descripteurs sont exprimés dans le langage de description objet FDL qui permet, notamment, l’expression de types de données complexes, définis sous la forme d’une aggrégation de classes de descripteurs, temporellement contrainte par des relations de Allen enrichies de cardinalités et de paramètres temporels. Comment alors, dans le cadre d’un développement objet, définir le lien de spécialisation de classes de descripteurs dont la définition contient de telles aggrégations ? Cet article présente la structure de classification de FDL, ainsi que son opérationnalisation au sein d’un système expert d’aide à la classification de classes de descripteurs audiovisuels. - Multimedia Authoring for Communities
of Teachers.
Agnès Guerraz, Cécile Roisin, Jan Mikác, Romain Deltour.
In International Journal of Web-Based Learning and Teaching Technologies, vol. 2 (3), pp. 1-18, July 2007. [bib, html]One way of providing technological support for communities of teachers is to help participants to produce, structure and share information. As this information becomes more and more multimedia in nature, the challenge is to build multimedia authoring and publishing tools that meets requirements of the community. In this paper we analyze these requirements and propose a multimedia authoring model and a generic platform on which specific community-oriented authoring tools can be realized. The main idea is to provide template-based authoring tools while keeping rich composition capabilities and smooth adaptability. It is based on a component-oriented approach integrating homogeneously logical, time and spatial structures. Templates are defined as constraints on these structures. - Décidabilité des requêtes
XPath avec contraintes de comptage.
Nebil Mabrouk.
Masters thesis, UJF, Grenoble, June 2007. [bib, pdf]L’émergence du langage XML comme standard pour la structuration et l’échange des données, a rendu nécessaire l’optimisation du langage XPath utilisé pour rechercher et extraire les informations dans les arbres XML. C’est dans ce contexte qu’intervient le problème d’analyse statique d’une logique capable de supporter XPath, auquel se réduisent les problèmes d’inclusion, d’équivalence, de jointure et de satisfaisabilité des requêtes XPath. En fait, pouvoir décider ce type de problèmes en un temps raisonnable permet d’aider à manipuler avec sûreté et efficacité les données XML et peut contribuer à réduire considérablement l’évaluation des requêtes XPath. Jusqu’à présent, les travaux menés par l’équipe WAM de l’INRIA ont permis de résoudre ces problèmes pour un fragment bien précis du langage XPath. Le but à long terme, est d’élargir progressivement le fragment étudié pour couvrir la totalité du langage XPath. L’étape primordiale qui est traitée dans ce mémoire est de considérer le problème de décidabilité pour les requêtes XPath avec contraintes de comptage. - Efficient Static Analysis of XML
Paths and Types.
Pierre Genevès, Nabil Layaïda, Alan Schmitt.
In PLDI ’07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pp. 342-351, ACM Press, June 2007. [bib, html, doi]We present an algorithm to solve XPath decision problems under regular tree type constraints and show its use to statically typecheck XPath queries. To this end, we prove the decidability of a logic with converse for finite ordered trees whose time complexity is a simple exponential of the size of a formula. The logic corresponds to the alternation free modal μ-calculus without greatest fixpoint, restricted to finite trees, and where formulas are cycle-free. Our proof method is based on two auxiliary results. First, XML regular tree types and XPath expressions have a linear translation to cycle-free formulas. Second, the least and greatest fixpoints are equivalent for finite trees, hence the logic is closed under negation. Building on these results, we describe a practical, effective system for solving the satisfiability of a formula. The system has been experimented with some decision problems such as XPath emptiness, containment, overlap, and coverage, with or without type constraints. The benefit of the approach is that our system can be effectively used in static analyzers for programming languages manipulating both XPath expressions and XML type annotations (as input and output types). - Engineering Multimedia Applications
on the basis of Multi-Structured Descriptions of Audiovisual Contents.
Marc Caillet, Jean Carrive, Cécile Roisin, François Yvon.
In Proceedings of the 2007 international workshop on Semantically aware document processing and indexing, ACM International Conference Proceedings Series; Vol. 259, pp. 31-40, ACM, May 2007. [bib, html]We focus our interest on the engineering of multimedia applications whose purpose is to exploit and make best use of the audiovisual heritage by means of prospective exploration of virtual access to audiovisual documents through multi-structured descriptions of these. Multi-structured descriptions are composed of multiple descriptors that are expressed using the FDL (Feria Description Language) object language whose expressive power is emphasized. FDL notably provides a multimedia developer with operations on descriptions and their inner descriptors, as well as temporal aggregation data types. An experimental multimedia application that makes extensive use of FDL concepts and mechanisms is outlined. It explores the use of syncing between the narrative structure of the text of a play and the narrative structure of different broadcasted performances of this play, at multiple granularity levels. - Multimedia Document Summarization
Based on a Semantic Adaptation Framework.
Sébastien Laborie, Jérôme Euzenat, Nabil Layaïda.
In Proceedings of the 2007 international workshop on Semantically aware document processing and indexing, ACM International Conference Proceeding Series; Vol. 259, pp. 87-94, ACM, May 2007. [bib, html]The multiplication of presentation contexts (such as mobile phones, PDAs) for multimedia documents requires the adaptation of document specifications. In an earlier work, a semantic framework for multimedia document adaptation was proposed. This framework deals with the semantics of the document composition by transforming the relations between multimedia objects. However, it was lacking the capability of suppressing multimedia objects. In this paper, we extend the proposed adaptation with this capability. Thanks to this extension, we present a method for summarizing multimedia documents. Moreover, when multimedia objects are removed, the resulted document satisfies some properties such as presentation contiguity. To validate our framework, we adapt standard multimedia documents such as SMIL documents. - Structured Templates for Authoring
Semantically Rich Documents.
Vincent Quint, Irène Vatton.
In Proceedings of the 2007 international workshop on Semantically aware document processing and indexing, ACM International Conference Proceeding Series; Vol. 259, pp. 41-48, ACM, May 2007. [bib, html]Structured documents associate explicit semantics with content, but authoring rigorously structured documents is a very difficult task. We present a new approach to this issue that adds schema-level information to the popular web formats. This makes editing highly structured documents easier, while ensuring that documents are valid. It is also an easy way to publish semantically rich documents on the web. The impact of this approach on authoring tools is discussed and its implementation in the Amaya editor is briefly presented. - Towards automatic XML structure
building for Web documents.
Agnès Guerraz.
INRIA Report 6035, February 2007. [bib, html]Web documents avalaible through the Internet are frequently supplied simply as poorly-written HTML or as plain text. Indeed, almost all of these Web documents are understandable only by humans, staying unexploitable by softwares and computers. The power of Semantic Web tools and XML technologies can only be deployed on documents having a minimum of formalism in their structure. This paper relates to the structuration process for Web documents that do not have a real structure through markup languages such as XML or definition of grammars for validing them. It deals with building of structure in documents when existing structure is insuficient or inexistant. This subject is closely related to the problems of automatic creation of XML schemas or templates. This work lies concretely within the scope of XML documents and their problems, related to the fact that their structure building and set up is time consuming for the user. Being based on techniques of data mining, information of structures is captured, clarifying and returning the names and the characteristics of structure elements, in particular their relationships, their constraints and their logical organization. This paper proposes a process which makes it possible to calculate automatically elements of structures (1) by applying methods of data mining on documents, (2) by building components of structure automatically, (3) by automatically proposing XML transformations on the final structured document. Initially, this work will use all the range of schemas going from XML schemas to templates. - XPath Typing Using a Modal Logic with
Converse for Finite Trees.
Pierre Genevès, Nabil Layaïda, Alan Schmitt.
In PLAN-X 2007, Programming Languages Technologies for XML, pp. 61-72, January 2007. [bib, pdf]We present an algorithm to solve XPath decision problems under regular tree type constraints and show its use to statically typecheck XPath queries. To this end, we prove the decidability of a logic with converse for finite ordered trees whose time complexity is a simple exponential of the size of a formula. The logic corresponds to the alternation free modal μ-calculus without greatest fixpoint restricted to finite trees where formulas are cycle-free. Our proof method is based on two auxiliary results. First, XML regular tree types and XPath expressions have a linear translation to cycle-free formulas. Second, the least and greatest fixpoints are equivalent for finite trees, hence the logic is closed under negation. With these proofs, we describe a practically effective system for solving the satisfiability of a formula. The system has been experimented with some decision problems such as XPath emptiness, containment, overlap, and coverage, with or without type constraints. The benefit of the approach is that our system can be effectively used in static analyzers for programming languages manipulating both XPath expressions and XML type annotations (as input and output types). - Logics for XML.
Pierre Genevès.
Ph.D. thesis, INPG, Grenoble, December 2006. [bib, pdf]This thesis describes the theoretical and practical foundations of a system for the static analysis of XML processing languages. The system relies on a fixpoint temporal logic with converse, derived from the μ-calculus, where models are finite trees. This calculus is expressive enough to capture regular tree types along with multi-directional navigation in trees, while having a single exponential time complexity. Specifically the decidability of the logic is proved in time $2^O(n)$ where $n$ is the size of the input formula. Major XML concepts are linearly translated into the logic: XPath navigation and node selection semantics, and regular tree languages (which include DTDs and XML Schemas). Based on these embeddings, several problems of major importance in XML applications are reduced to satisfiability of the logic. These problems include XPath containment, emptiness, equivalence, overlap, coverage, in the presence or absence of regular tree type constraints, and the static type-checking of an annotated query. The focus is then given to a sound and complete algorithm for deciding the logic, along with a detailed complexity analysis, and crucial implementation techniques for building an effective solver. Practical experiments using a full implementation of the system are presented. The system appears to be efficient in practice for several realistic scenarios. The main application of this work is a new class of static analyzers for programming languages using both XPath expressions and XML type annotations (input and output). Such analyzers allow to ensure at compile-time valuable properties such as type-safety and optimizations, for safer and more efficient XML processing. - A Spatial Algebra for Multimedia
Document Adaptation.
Sébastien Laborie, Jérôme Euzenat, Nabil Layaïda.
In Proceedings of the 1st International Conference on Semantic and Digital Media Technologies (SAMT), December 2006. [bib, html]The multiplication of execution contexts for multimedia documents requires the adaptation of document specifications. This paper instantiates our previous semantic approach for multimedia document adaptation to the spatial dimension of multimedia documents. Our goal is to find a qualitative spatial representation that computes, in a reasonable time, a set of adaptation solutions close to the initial document satisfying a profile. The quality of an adaptation can be regarded in two respects: expressiveness of adaptation solutions and computation speed. In this context, we propose a new spatial representation sufficiently expressive to adapt multimedia documents faster. - A System for the Static Analysis of
XPath.
Pierre Genevès, Nabil Layaïda.
In ACM Transactions on Information Systems (TOIS), vol. 24 (4), pp. 475-502, October 2006. [bib, html]XPath is the standard language for navigating XML documents and returning a set of matching nodes. We present a sound and complete decision procedure for containment of XPath queries as well as other related XPath decision problems such as satisfiability, equivalence, overlap and coverage. The considered XPath fragment covers most of the language features used in practice. Specifically, we propose a unifying logic for XML, namely the alternation-free modal μ-calculus with converse. We show how to translate major XML concepts such as XPath and regular XML types (including DTDs) into this logic. Based on these embeddings, we show how XPath decision problems, in the presence or the absence of XML types, can be solved using a decision procedure for μ-calculus satisfiability. We provide a complexity analysis together with practical experiments of our system that illustrate the efficiency of the approach for realistic scenarios. - Multimedia Authoring for CoPs.
Romain Deltour, Agnès Guerraz, Cécile Roisin.
In TEL-CoPs’06, 1st International Workshop on Building Technology Enhanced Learning solutions for Communities of Practice, October 2006. [bib, pdf]One way of providing technological support for CoPs is to help participants to produce, structure and share information. As this information becomes more and more multimedia in nature, the challenge is to build multimedia authoring and publishing tools that meets CoPs requirements. In this paper we analyze these requirements and propose a multimedia authoring model and a generic platform on which specific CoPs-oriented authoring tools can be realized. The main idea is to provide template-based authoring tools while keeping rich composition capabilities and smooth adaptability. It is based on a component-oriented approach integrating homogeneously logical, time and spatial structures. Templates are defined as constraints on these structures. - The LimSee3 Multimedia Authoring
Model.
Romain Deltour, Cécile Roisin.
In Proceedings of the 2006 ACM Symposium on Document Engineering, DocEng 2006, pp. 173-175, ACM Press, October 2006. [bib, pdf, doi]For most users, authoring multimedia documents remains a complex task. One solution to deal with this problem is to provide template-based authoring tools but with the drawback of limited functionality. In this paper we propose a document model dedicated to the creation of authoring tools using templates while keeping rich composition capabilities. It is based on a component oriented approach integrating homogeneously logical, time and spatial structures. Templates are defined as constraints on these structures. - Comparing XML Path Expressions.
Pierre Genevès, Nabil Layaïda.
In Proceedings of the 2006 ACM Symposium on Document Engineering, DocEng 2006, pp. 65-74, ACM Press, October 2006. [bib, pdf, doi]XPath is the standard declarative language for navigating XML data and returning a set of matching nodes. In the context of XSLT/XQuery analysis, query optimization, and XML type checking, XPath decision problems arise naturally. They notably include XPath comparisons such as equivalence (whether two queries always return the same result), and containment (whether for any tree the result of a particular query is included in the result of a second one). XPath decision problems have attracted a lot of research attention, especially for studying the computational complexity of various XPath fragments. However, what is missing at present is the constructive use of an expressive logic which would allow capturing these decision problems, while providing practically effective decision procedures. In this paper, we propose a logic-based framework for the static analysis of XPath. Specifically, we propose the alternation free modal μ-calculus with converse as the appropriate logic for effectively solving XPath decision problems. We present a translation of a large XPath fragment into μ-calculus, together with practical experiments on the containment using a state-of-the-art EXPTIME decision procedure for μ-calculus satisfiability. These preliminary experiments shed light, for the first time, on the cost of checking the containment in practice. We believe they reveal encouraging results for further static analysis of XML transformations. - Templates, Microformats and Structured
Editing.
Francesc Flores, Vincent Quint, Irène Vatton.
In Proceedings of the 2006 ACM Symposium on Document Engineering, DocEng 2006, pp. 188-197, ACM Press, October 2006. [bib, html]Microformats and semantic XHTML add semantics to web pages while taking advantage of the existing (X)HTML infrastructure. This approach enables new applications that can be deployed smoothly on the web. But there is currently no way to describe rigorously this type of markup and authors of web pages have very little help for creating and encoding semantic markup. A language that addresses these issues is presented in this paper. Its role is to specify semantically rich XML languages in terms of other XML languages, such as XHTML. The language is versatile enough to represent templates that can capture the overall structure of large documents as well as the fine details of a microformat. It is supported< markup language, still fully compatible with XHTML. - XTiger : Templates, Microformats
et d’Autres (Petites) Choses.
Francesc Flores.
Masters thesis, UJF, Grenoble, June 2006. [bib, pdf] - Mu-Calculus Based Resolution
of XPath Decision Problems.
Pierre Genevès, Nabil Layaïda.
INRIA Report 5868, March 2006. [bib, pdf]XPath is the standard declarative notation for navigating XML data and returning a set of matching nodes. In the context of XSLT/XQuery analysis, query optimization, and XML type checking, XPath decision problems arise naturally. They notably include XPath containment (whether or not for any tree the result of a particular query is included in the result of a second one), and XPath satisfiability (whether or not an expression yields a non-empty result), in the presence (or the absence) of XML DTDs. In this paper, we propose a unifying logic for XML, namely the alternation-free modal μ-calculus with converse. We show how to translate major XML concepts such as XPath and DTDs into this logic. Based on these embeddings, we show how XPath decision problems can be solved using a state-of-the-art EXPTIME decision procedure for μ-calculus satisfiability. We provide preliminary experiments which shed light, for the first time, on the cost of solving XPath decision problems in practice. - A Decision Procedure for XPath
Containment.
Pierre Genevès, Nabil Layaïda.
INRIA Report 5867, March 2006. [bib, pdf]XPath is the standard language for addressing parts of an XML document. We present a sound and complete decision procedure for containment of XPath queries. The considered XPath fragment covers most of the language features used in practice. Specifically, we show how XPath queries can be translated into equivalent formulas in monadic second-order logic. Using this translation, we construct an optimized logical formulation of the containment problem, which is decided using tree automata. When the containment relation does not hold between two XPath expressions, a counter-example XML tree is generated. We provide a complexity analysis together with practical experiments that illustrate the efficiency of the decision procedure for realistic scenarios. - Adaptation spatiale efficace de
documents SMIL.
Sébastien Laborie, Jérôme Euzenat, Nabil Layaïda.
In RFIA 2006, January 2006. [bib, pdf]The multiplication of execution contexts for multimedia x-proceedings = yes, x-international-audience = no, documents requires the adaptation of document specifications to the particularities of the contexts. We proposed a semantic approach to multimedia document adaptation which was temporally defined with regards to the Allen algebra of relations. This paper extends this framework to the spatial dimension of SMIL documents. Our goal is to find a qualitative spatial representation that computes a set of adaptation solutions close to the initial document respecting the adaptation constraints. The quality of an adaptation can be regarded on two respects : expressiveness of adaptation solutions and computation speed. In this context, we characterize the adaptation quality of existing spatial representations. We show that these representations do not allow for optimal quality. Thus, we propose a new spatial representation which is sufficiently expressive to adapt SMIL documents faster. - NAC, une architecture pour
l’adaptation multimédia sur le web.
Nabil Layaïda, Tayeb Lemlouma, Vincent Quint.
In Technique et Science Informatiques (TSI), vol. 24 (7), pp. 789-813, 2005. [bib, pdf]The Web is evolving towards richer contents and diverse media that are accessed with different devices through multiple kinds of network. This heterogeneous, mobile and changing environment requires that multimedia information delivered by servers be adapted to the actual conditions of use. For that purpose, a number of methods, languages, formats and protocols are developed, especially by W3C. The NAC architecture presented in this article was designed and implemented based on these technologies, focusing on adaptation processing, on environment description models, on negotiation protocols, and on content transformations. - Synchronized Multimedia
Integration Language (SMIL 2.1).
Dick Bulterman, Guido Grassel, Jack Jansen, Antti Koivisto, Nabil Layaïda, Thierry Michel, Sjoerd Mullender, Daniel Zucker.
World Wide Web Consortium Report, December 2005. [bib, html]This document specifies the second version of the Synchronized Multimedia Integration Language (SMIL, pronounced "smile"). SMIL 2.1 has the following design goals: 1) Define an XML-based language that allows authors to write interactive multimedia presentations. Using SMIL, an author can describe the temporal behaviour of a multimedia presentation, associate hyperlinks with media objects and describe the layout of the presentation on a screen. 2) Allow reusing of SMIL syntax and semantics in other XML-based languages, in particular those who need to represent timing and synchronization. For example, SMIL components are used for integrating timing into XHTML and into SVG. 3) Extend the functionalities contained in the SMIL 2.0 into new or revised SMIL 2.1 modules. 4) Define new SMIL 2.1 Mobile Profiles incorporating features useful within the mobile industry. - SMIL 2.1 Language Profile.
Nabil Layaïda.
World Wide Web Consortium Report, December 2005. [bib, html]The SMIL 2.1 Language Profile describes the SMIL 2.1 modules that are included in the SMIL 2.1 Language and details how these modules are integrated. It contains support for all of the major SMIL 2.1 features including animation, content control, layout, linking, media object, meta-information, structure, timing and transition effects. It is designed for Web clients that support direct playback from SMIL 2.1 markup. - SMIL 2.1 Basic Profile and
Scalability Framework.
Nabil Layaïda.
World Wide Web Consortium Report, December 2005. [bib, html]SMIL 2.1 provides a scalability framework, where a family of scalable SMIL profiles can be defined using subsets of the SMIL 2.1 language profile. A SMIL document can be authored conforming to a scalable SMIL profile such that it provides limited functionality on a resource-constrained device while allowing richer capabilities on a more capable device. SMIL 2.1 Basic (or SMIL Basic) is a profile that meets the needs of resource-constrained devices such as minimum capability mobile phones. The SMIL Basic profile provides the basis for defining scalable SMIL profiles. SMIL Basic is SMIL host language conformant. It consists of precisely those modules that are required for SMIL host language conformance. This section defines the SMIL 2.1 Basic profile and requirements for conforming SMIL Basic documents and SMIL Basic user agents. More, it describes scalable SMIL profiles, guidelines for defining them, and their conformance requirements. - Content Interaction and Formatting
for Mobile Devices.
Tayeb Lemlouma, Nabil Layaïda.
In Proceedings of the 2005 ACM Symposium on Document Engineering, DocEng 2005, pp. 98-100, ACM Press, November 2005. [bib, pdf, doi]In this paper we present a content adaptation system for mobile devices. The system enables the presentation of multimedia content and considers the problem of small screen display of mobile terminals. The approach combines structural and media adaptation with the content formatting and proposes a system that handles the user interaction and the content navigation. - Compiling XPath for Streaming Access
Policy.
Pierre Genevès, Kristoffer Rose.
In Proceedings of the 2005 ACM Symposium on Document Engineering, DocEng 2005, pp. 52-54, ACM Press, November 2005. [bib, pdf, doi]We show how the full XPath language can be compiled into a minimal subset suited for stream-based evaluation. Specifically, we show how XPath normalization into a core language as proposed in the current W3C Last Call draft of the XPath/XQuery Formal Semantics can be extended such that both the context state and reverse axes can be eliminated from the core XPath (and potentially XQuery) language. This allows execution of (almost) full XPath on any of the emerging streaming subsets. - Towards Active Web Clients.
Vincent Quint, Irène Vatton.
In Proceedings of the 2005 ACM Symposium on Document Engineering, DocEng 2005, pp. 168-176, ACM Press, November 2005. [bib, pdf, doi]Recent developments of document technologies have strongly impacted the evolution of Web clients over the last fifteen years, but all Web clients have not taken the same advantage of this advance. In particular, mainstream tools have put the emphasis on accessing existing documents to the detriment of a more cooperative usage of the Web. However, in the early days, Web users were able to go beyond browsing and to get more actively involved. This paper presents the main features needed to make Web clients more active and creative tools, by taking advantage of the latest advances of document technology. These features are implemented in Amaya, a user agent that supports several languages from the XML family and integrates seamlessly such complementary functionalities as browsing, editing, publishing, and annotating. - Integrating Translation Services
within a Structured Editor.
Ali Choumane, Hervé Blanchon, Cécile Roisin.
In Proceedings of the 2005 ACM Symposium on Document Engineering, DocEng 2005, pp. 165-167, ACM Press, November 2005. [bib, pdf, doi]Fully automatic machine translation cannot produce high quality translation; Dialog-Based Machine Translation (DB-MT) is the only way to provide authors with a means of translating documents in languages they have not mastered, or do not even know. With such environment, the author must help the system to understand the document by means of an interactive disambiguation step. In this pa- per we study the consequences of integrating the DBMT services within a structured document editor (Amaya). The source document (named edited document) needs a compan- ion document enriched with dierent data produced during the interactive translation process (question trees, answers of the author, translations). The edited document also needs to be enriched (annotated) in order to enable access to the question trees. The enriched edited document and the com- panion document have to be synchronized in case the edited document is further updated. - PACE: an Experimental Web-Based
Audiovisual Application using FDL.
Marc Caillet, Jean Carrive, Vincent Brunie, Cécile Roisin.
In Web Document Analysis 2005, August 2005. [bib, pdf]This paper describes the PACE experimental multimedia application that aims at providing automatic tools for web browsing of television program collections; experimentations are currently in progress with a fifty-four Le Grand Échiquier show collection. PACE has been built with the FERIA framework and relies on multiple automatic analysis tools. It is generic enough to easily adapt to other collections. Emphasis is made on the new audiovisual documents description language FDL as it is the core part of FERIA, with a particular attention paid on how it operates in PACE. - LimSee2: A Cross-Platform SMIL
Authoring Tool.
Romain Deltour, Nabil Layaïda, Daniel Weck.
In ERCIM News, pp. 41-42, July 2005. [bib, html]LimSee2 is an open-source and cross-platform authoring tool dedicated to the manipulation of time-based multimedia documents for the Web. It relies on the SMIL standard of the World Wide Web Consortium (W3C). - Adapter temporellement un document
SMIL.
Sébastien Laborie, Jérôme Euzenat, Nabil Layaïda.
In Atelier Connaissance et Documents Temporels, AFIA 2005, pp. 47-58, May 2005. [bib, pdf]Les récentes avancées technologiques permettent aux documents multimédia d’être présentés sur de nombreuses plates-formes (ordinateurs de bureau, PDA, téléphones portables. . .). Cette diversification des supports a entraîné un besoin d’adaptation des documents à leur contexte d’exécution. Une approche sémantique d’adaptation de documents multimédia a été proposée et temporellement définie à l’aide de l’algèbre d’intervalles d’Allen. Cet article étend ces précédents travaux en les appliquant au langage de spécification de documents multimédia SMIL. Pour cela, des fonctions de traduction de SMIL vers l’algèbre de Allen (et inversement) ont été définies. Celles-ci préservent la proximité entre le document adapté et le document initial. - Description des documents
audiovisuels: s’affranchir des limitations de MPEG-7.
Marc Caillet, Jean Carrive, Cécile Roisin.
In MetSI/Inforsid, May 2005. [bib, pdf]The National Institute of Audiovisual (INA) has to face the consequences of audiovisual contents digitalization. Among those consequences, new access modes to audiovisual content are defining a class of new multimedia applications, focused on content description. This article evaluates the standard multimedia description language MPEG-7 as an applicant to fulfill our needs of expressiveness. Coming to the conclusion that it’s not fulfilling them all, we propose our own language, FDL, as an alternative. - Le temps dans les documents - Langage
SMIL.
Nabil Layaïda, Cécile Roisin.
In Document numériques – Gestion de contenu, Techniques de l’Ingénieur, 2004. [bib, html]La production et l’accès de plus en plus aisé aux contenus multimédias numériques suscitent naturellement l’envie de les intégrer pour réaliser des « documents multimédias » dans lesquels le sens est apporté non seulement par le contenu de chacun des éléments de la présentation mais aussi par la synchronisation (spatiale et/ou temporelle) et les liens de navigation entre ces éléments. Depuis plusieurs années, un effort important de recherche et de standardisation de ces formats d’intégration a été apporté (SMIL, MPEG4). Les éléments de contenu eux-mêmes font l’objet de standard pour enrichir leur niveau de description (MPEG7). Dans ce chapitre, nous présentons les concepts et les besoins liés à l’introduction d’une dimension temporelle dans les documents électroniques, ainsi que les solutions actuelles apportées à ce domaine : outils existants, standards, prototypes de recherche. Tirant parti des possibilités offertes par ces techniques, nous étudions les besoins des utilisateurs à différents niveaux de la chaîne de production des présentations et montrons comment les outils répondent à ces attentes, en particulier en matière de pouvoir d’expression, de réutilisation et de facilité d’édition. Ce document est organisé en quatre grandes parties : une introduction générale sur la notion de documents multimédia et des domaines d’application concernés, l’étude des caractéristiques et des fonctions souhaitées pour la spécification de documents multimédia, l’étude détaillée du format standard SMIL et enfin la présentation de différents outils de présentation et d’édition de documents multimédia. - Proceedings of the 2004 ACM
Symposium on Document Engineering.
Editors: Jean-Yves Vion-Dury.
ACM Press, October 2004. [bib] - Logic-Based XPath Optimization.
Pierre Genevès, Jean-Yves Vion-Dury.
In Proceedings of the 2004 ACM symposium on Document Engineering, DocEng 2004, pp. 211-219, ACM Press, October 2004. [bib, pdf, doi]XPath was introduced by the W3C as a standard language for specifying node selection, matching conditions, and for computing values from an XML document. XPath is now used in many XML standards such as XSLT and the forthcoming XQuery database access language. Since efficient XML content querying is crucial for the performance of almost all XML processing architectures, a growing need for studying high performance XPath-based querying has emerged. Our approach aims at optimizing XPath performance through static analysis and syntactic transformation of XPath expressions. - Techniques for Authoring Complex XML
Documents.
Vincent Quint, Irène Vatton.
In Proceedings of the 2004 ACM symposium on Document Engineering, DocEng 2004, pp. 115-123, ACM Press, October 2004. [bib, pdf, doi]This paper reviews the main innovations of XML and considers their impact on the editing techniques for structured documents. Namespaces open the way to compound documents; well-formedness brings more freedom in the editing task; CSS allows style to be associated easily with structured documents. In addition to these innovative features, the wide deployment of XML introduces structured documents in many new applications, including applications where text is not the dominant content type. In languages such as SVG or SMIL, for instance, XML is used to represent vector graphics or multimedia presentations. This is a challenging situation for authoring tools. Traditional methods for editing structured documents are not sufficient to address the new requirements. New techniques must be developed or adapted to allow more users to efficiently create advanced XML documents. These techniques include multiple views, semantic-driven editing, direct manipulation, concurrent manipulation of style and structure, and integrated multi-language editing. They have been implemented and experimented in the Amaya editor and in some other tools. - Adaptation aux différents modes de
lecture.
Cécile Roisin.
In Publier sur Internet, INRIA summer school, pp. 129-155, ADBS éditions, September 2004. [bib, pdf]L’objectif de ce module est de présenter les formats et les solutions qui permettent de publier des contenus structurés et adaptables sur le web. Dans une première partie, nous nous attachons à décrire les principes qui sous-tendent à la définition des formats de documents, puis nous présentons plus précisément quelques formats standard, depuis les formats des contenus de base (texte) jusqu’aux formats d’intégration (XHTML, SMIL), en passant par des formats d’objets structurés (MATHML, SVG). Dans une deuxième partie, nous montrons dans quelle mesure ces formats permettent ou non de définir des présentations indépendamment de leur restitution physique qui dépend de type de terminal de lecture (écran, papier, pda, téléphone). Nous appuyons notre étude des besoins à partir des travaux standard sur l’accessibilité, l’internationalisation et le device independence. Puis, nous décivons quelques techniques d’adaptation à travers l’étude des possibilités offertes par les langages XSLT et SMIL. - Outils pour la production de
présentations hypermédias.
Cécile Roisin.
In Les hypermédias : théorie et pratique, Hermès, September 2004. [bib, pdf]Even if multimedia contents are widely used and standard formats exist both for media items and presentation structures, there is still a gap between user requirements and existing tools. In this chapter we examine what are the user needs for specification, management and editing of multimedia documents. We illustrate our discussion with the SMIL language and its players and authoring tools. - XPath Formal Semantics and Beyond: a
Coq based approach.
Pierre Genevès, Jean-Yves Vion-Dury.
In Proceedings of the 17th International Conference on Theorem Proving in Higher Order Logic: TPHOLs 2004, pp. 181-198, University of Utah, August 2004. [bib, pdf]XPath was introduced as the standard language for addressing parts of XML documents, and has been widely adopted by practioners and theoreticaly studied. We aim at building a logical framework for formal study and analysis of XPath and have to face the combinatorial complexity of formal proofs caused by XPath expressive power. We chose the Coq proof assistant and its powerful inductive constructions to rigorously investigate XPath peculiarities. We focus in this paper on a basic modeling of XPath syntax and semantics, and make two contributions. First, we propose a new formal semantics, which is an interpretation of paths as first order logic propositions that turned out to greatly simplify our formal proofs. Second, we formally prove that this new interpretation is equivalent to previously known XPath denotational semantics, opening perspectives for more ambitious mathematical characterizations. We illustrate our Coq based model through several examples and we develop a formal proof of a simple yet significant XPath property that compares quite favorably to a former informal proof. - Improving Efficiency of XPath-Based
XML Querying.
Pierre Genevès.
In IFIP 18th World Computer Congress, Student Forum, pp. 143-153, Kluwer Academic Publishers, August 2004. [bib, pdf]XML is becoming the de facto standard for information exchange. XML querying is a key component for structured information processing and plays a central role in the next generation world wide web, information management systems and databases. Applications relying on XML processing notably depend on XPath, the standard language for adressing parts of XML documents. Besides its fundamental functionality, reasons behind XPath suc- cess include being widely accepted by programmers and well-suited for formal treatments. With the growing volume of XML content and XML processing applications, our research is oriented toward efficiency of XML querying. Our approach relies on analysis and trans- formation of XPath expressions for optimization. This note presents current open issues with XPath, and introduces our preliminary results applied to streaming XPath processing. Moreover, it describes our methodology, which includes XPath modelisation using the Coq proof assistant, and future directions envisioned toward high performance XML querying. - Réflexions sur la modélisation des
documents.
Veronika Lux-Pogodalla, Jean-Yves Vion-Dury.
In Information - Interaction - Intelligence, vol. 4 (1), 2004. [bib, pdf]Today, we more than ever need useful abstractions in order to reason on complex document transformations, to assert properties on document manipulation systems, and to inspire perhaps revolutionary approaches of document creation and processing. This paper sketches perspectives and proposes markers toward inventing the next document generation. - Architecture de Négociation et
d’Adaptation de Services Multimédia dans des Environnements
Hétérogènes.
Tayeb Lemlouma.
Ph.D. thesis, INPG, Grenoble, June 2004. [bib, pdf]In the last few years, new devices such as palm computers, smart phones, pocket PCs became common components of the computing infrastructure. These devices allow multimedia information to be used on the Web at any time and anywhere. At the same time, the content of the Web has known an important revolution. Today, the Web includes continuous medias such as video, audio and 3D animations. The content is created in several formats with new functionalities. Usually, these formats are based on many structural dimensions: logical, spatial, temporal and hypermedia. In order to ensure universal access to Web content, with respect to the constraints of the current environment, it is necessary to design new systems that enable content delivery in different contexts. The objective of our work is to resolve the problems related to content adaptation and negotiation based on the limitations of the target devices and the heterogeneous environment. We propose a flexible architecture called NAC that includes different components for content negotiation and adaptation, and ensures an efficient framework in which these components cooperate and exchange negotiation-based information in order to reach the objective of the universal access. NAC allows several kinds of adaptations to be applied: structural adaptation, semantic adaptation and media resources adaptation. These adaptations satisfy different contexts of the clients. We also propose a description model of the environment context: UPS, a negotiation protocol and a rich collection of adaptation techniques. NAC concepts have contributed in W3C standardization efforts, in particular in the CC/PP framework and in work on Device Independence. This work includes performance evaluations in order to show the usability of our system in a practical framework. - Compound XML Documents in Amaya.
Vincent Quint, Irène Vatton.
In W3C Workshop on Web Applications and Compound Documents, June 2004. [bib, html]Amaya is an authoring tool for editing compound XML documents. We first briefly explain how several XML markup languages can be mixed in a document created by Amaya. Then we discuss the various editing modes available for handling this compound structure. In particular, the concept of a view is introduced as well as its connection with editing. This is followed by a short discussion of the role of CSS in complex structures, and a conclusion summarizes the advantages offered by an integrated environment. - Logic-Based XPath Optimization.
Pierre Genevès, Jean-Yves Vion-Dury.
In First International Workshop on High Performance XML Processing, May 2004. [bib, pdf]XPath was introduced by the W3C as a standard language for specifying node selection, matching conditions, and for computing values from an XML document. XPath is now used in many XML standards such as XSLT or the forthcoming XQuery database access language. Since efficient XML content querying is crucial for the performance of almost all XML processing architectures, a growing need for studying high performance XPath-based querying has emerged. Our approach aims at optimizing XPath performance through static analysis and syntactic transformation of XPath expressions. - Compiling XPath into a State-less
Forward-only Subset.
Pierre Genevès, Kristoffer Rose.
In First International Workshop on High Performance XML Processing, May 2004. [bib, pdf]We show how the context state of XPath, accessed through the position() and last() pseudo-functions, can be eliminated in most cases by translating references to the context state with an equivalent contextfree expression, and how this enables the use of context state in combination with a subsequent forward-only transformation, allowing for execution of (almost) full XPath on any of the emerging streaming subsets. Specifically we show how the normalization into a core language as proposed in the current W3C Last Call draft of the XPath/XQuery Formal Semantics can be extended such that the context state and reverse axes can be eliminated from the core XPath (and potentially XQuery) language. - Adaptation et multimédia mobile sur le
Web.
Nabil Layaïda, Tayeb Lemlouma, Vincent Quint.
In Conférence nationale sur le multimédia mobile, Mcube 2004, pp. 34-41, March 2004. [bib, html]The Web is evolving towards multimedia contents accessed through various kinds of devices and very different networks. Multimedia information must be adapted to this mobile and changing environment. For this purpose, a set of methods, languages, formats, and protocols are developed, mainly by W3C. We have defined and implemented the NAC architecture grounded on these technologies, focusing on the distribution of adaptation processing, on the models and languages for environment description and on content transformation. - Authoring Techniques for Device
Independence.
R Hanrahan, R Merrick.
World Wide Web Consortium Report, February 2004. [bib, html]The document provides a summary of several techniques and best practices that Web site authors and solution providers may employ when creating and delivering content to a diverse set of access mechanisms. - Context-Aware Adaptation for Mobile
Devices.
Tayeb Lemlouma, Nabil Layaïda.
In MDM2004 International Conference on Mobile Data Management, pp. 106-111, IEEE, January 2004. [bib, pdf]This paper discusses the problem of content adaptation for mobile devices. The adaptation considers the context of the client and also the environment where the client request is received. A device independent model is defined and used in order to achieve automatic adaptation of the content based on its semantic and the capabilities of the target device. Our system includes a context description model and a client repository and offers device contexts management and querying functions. The proposed system uses the XQuery language to query the profiles and delivers the results in the form of SOAP services. - Proceedings of the 2003 ACM
Symposium on Document Engineering.
Editors: Christine Vanoirbeek, Cécile Roisin, Ethan Munson.
ACM Press, November 2003. [bib] - Improving Formatting Documents by
Coupling Formatting Systems.
Fateh Boulmaiz, Cécile Roisin, Frédéric Bès.
In Proceedings of the 2003 ACM Symposium on Document Engineering, DocEng2003, pp. 92-94, ACM Press, November 2003. [bib, pdf, doi]In this paper, we present a framework for coupling an existing formatting system such as SMIL or Madeus with a formatting control system called XEF. This framework allows the coupling process to be performed at two levels: 1) the language level, which is concerned with how to link the control features of XEF and the elements of an existing formatting system, and 2) the formatter level, which deals with the creation of a new formatter by formatter composition. The overall objective is to provide more powerful and flexible formatting services to cover new needs such as adaptive and/or generated presentations. - XPath on Left and Right Sides of
Rules: Toward Compact XML Tree Rewriting through Node Patterns.
Jean-Yves Vion-Dury.
In Proceedings of the 2003 ACM Symposium on Document Engineering, DocEng2003, pp. 19-25, ACM Press, November 2003. [bib, pdf, doi]XPath is a powerful and quite successful language able to perform complex node selection in trees through compact specifications. As such, it plays a growing role in many areas ranging from schema specifications, designation and transformation languages to XML query languages. Moreover, researchers have proposed elegant and tractable formal semantics, fostering various works on mathematical properties and theoretical tools. We propose here a novel way to consider XPath, not only for selecting nodes, but also for tree rewriting using rules. In the rule semantics we explore, XPath expressions are used both on the left and on the right side. We believe that this proposal opens new perspectives toward building highly concise XML transformation languages on widely accepted basis. - Le langage SMIL au service des Sciences
Humaines et Sociales.
Vincent Kober, Daniel Weck, Cécile Roisin.
In JRES 2003, pp. 341-353, November 2003. [bib, pdf]This article present the result of a collaboration between a research team of INRIA which works in particular on the multimedia presentation of synchronized documents and a team of historians having needs in this domain. Without being an exhaustive study of a language, we show through the needs expressed by the historians researchers, how the use of technologies and the tools related to language SMIL (Synchronized Multimedia Integration Language) meets the needs for implementation of this type of presentation. This article also describes the principal tools making it possible to write and play SMIL documents while insisting on the authoring tool LimSee2 developed in WAM project. - Multimedia Modeling Using MPEG-7
for Authoring Multimedia Integration.
Tien Tran-Thuong, Cécile Roisin.
In 5th ACM SIGMM International Workshop on Multimedia Information Retrieval (ACM MIR’03), pp. 171-178, ACM Press, November 2003. [bib, pdf, doi]In this paper, we describe an approach to audiovisual data modeling for multimedia integration and synchronization. The approach chosen consists in using description tools from Multimedia Description Schemes of standard MPEG-7 to describe audiovisual contents and in integrating these description models into a multimedia integration and synchronization model close to SMIL. The resulting model provides relevant specification tools for the fine integration of multimedia fragments into multimedia presentations. An authoring environment illustrates the authoring features that can be obtained thanks to these integrated models. - Hypermédia et technologies Web.
Vincent Quint.
In Hypertextes hypermédias, actes de H2PTM’03, pp. 381-390, Hermès Science, September 2003. [bib, html]Since more than ten years the Web has turned hypertext and multimedia into very popular technologies. More recent evolutions of the Web, all related to XML, have broadened the field of hypermedia. These new technologies provide information with a strong structure. They bring new graphical possibilities on many kinds of devices. They allow new applications to handle hypermedia documents. They make these documents more dynamic and provide more sophisticated hypertext links. All these evolutions are analyzed in this article. - A semantic framework for multimedia
document adaptation.
Jérôme Euzenat, Nabil Layaïda, Victor Dias.
In Proceedings of the 18th International Joint Conference on Artificial Intelligence IJCAI’2003, pp. 31-36, Morgan Kauffman, August 2003. [bib, pdf]With the proliferation of heterogeneous devices (desktop computers, personal digital assistants, phones), multimedia documents must be played under various constraints (small screens, low bandwidth). Taking these constraints into account with current document models is impossible. Hence, generic source documents must be transformed into documents compatible with the target contexts. Currently, the design of transformations is left to programmers. We propose here a semantic framework, which accounts for multimedia document adaptation in very general terms. A model of a multimedia document is a potential execution of this document and a context defines a particular class of models. The adaptation should then retain the source document models that belong to the class defined by the context if such models exist. Otherwise, the adaptation should produce a document whose models belong to this class and are "close" to those of the source documents. We focus on the temporal dimension of multimedia documents and show how adaptation can take advantage of temporal reasoning techniques. Several metrics are given for assessing the proximity of models. - Containment of XPath expressions: an
Inference and Rewriting based approach.
Jean-Yves Vion-Dury, Nabil Layaïda.
In Extreme Markup Languages, IDEAlliance, August 2003. [bib, pdf]XPath is a simple query language for XML documents which allows navigating in XML trees and returning a set of matching nodes. It is used in XML Schema to define keys an in XLink and XPointer to reference portions of documents. XPath is a fundamental part of XSLT and XQuery languages as it allows to define matching expressions for patterns and provides node selectors to filter elements in the transformations. We propose to study the containment and equivalence of XPath expressions using an inference system combined with a rewriting system. The inference system allows to assert and prove properties on a class of expressions. In order to keep the proof system compact, we propose a re-writing architecture which allows to transform remaining expressions in a disjunctive normal form compatible with this class. In contrast with model based approaches, the inference and rewriting systems are applied to the XPath language directly. We believe this will help understanding the underlying issues of deciding containment on the language itself. - A framework for aligning and indexing
movies with their script.
Remi Ronfard, Tien Tran-Thuong.
In Proceedings of IEEE International Conference on Multimedia and Expo (ICME), IEEE Computer Society, July 2003. [bib, pdf]A continuity script describes very carefully the content of a movie shot by shot. This paper introduces a framework for extracting structural units such as shots, scenes, actions and dialogs from the script, and aligning them to the movie based on the longest matching subsequence between them. We present experimental results and applications of the framework with a full-length movie and discuss its applicability to large-scale film repositories. - Encoding Multimedia Presentation for
User Preferences and Limited Environments.
Tayeb Lemlouma, Nabil Layaïda.
In Proceedings of IEEE International Conference on Multimedia and Expo (ICME), pp. 165-168, IEEE Computer Society, July 2003. [bib, pdf]This paper discusses a new approach of generating TV-like multimedia presentations that are adapted to the target user preferences and to limited devices. Three main points are discussed: 1) The encoding of video presentations from a SMIL specification 2) The adaptation of the video content based on the user preferences, and 3) The delivery of adapted multimedia presentations. The used architecture includes a content server, an adaptation proxy and a set of small devices in the form of personal device assistants (PDA). These devices request the content through a wireless network. In order to show how the system behaves regarding the user preferences and capabilities, two negotiation dimensions are considered: the user language and the memory capability of the device. The first dimension is used to generate a content that can be understood by the target user, e.g. a video with subtitles written in the preferred language. The second dimension is chosen to solve the problem of the system blocking that usually happens when limited devices access rich multimedia presentations over the network. - NAC: An Architecture for Multimedia
Content Adaptation for Mobile Devices.
N Layaida, T Lemlouma.
In ERCIM News, July 2003. [bib, pdf]In the current web infrastructure, access to content is achieved from a variety of terminals such as desktop PCs, smart phones, set top boxes and personal digital assistants (PDAs). The different capabilities of these terminals led to the development of a variety of parallel webs each one accommodating a particular device feature. This situation poses a serious problem to web designers and maintainers since every piece of information needs to be authored for every type of terminal with the associated protocols. Our research work in the WAM project at INRIA is an attempt to unify web access to information with a more flexible and negotiated approach. - Media Resources Adaptation for
Limited Devices.
Tayeb Lemlouma, Nabil Layaïda.
In Proceedings of the 7th ICCC/IFIP International Conference on Electronic Publishing, ELPUB 2003, pp. 209-218, Universidade deo Minho, June 2003. [bib, pdf]In this paper, we define a framework for media resources manipulation in an adaptive content delivery system. We discuss the media resources manipulation in an adaptation and negotiation architecture in terms of binary relationship definition using a so-called "related resources" approach, resources extraction, adaptation and delivery. We show how different resources can be related by predefined semantic relationships in order to help structural adaptation and content negotiation tasks. We give a simple recursive algorithm to extract media resources form an input tree structure. The media description is specified using an extensible CC/PP profile. In order to show the benefits of our approach, we give a practical application of media manipulation: an automatic adaptation of XHTML documents for mobile phones. We propose also a general mechanism for the content servers in order to deliver media resources according to client constraints or profile. The influence of media selection in the delivery of multimedia services is also described using evaluation formulae and measured with some experimentations. - Couplage d’un langage de
contrôle de formatage avec un système de formatage.
Fateh Boulmaiz.
Masters thesis, UJF, Grenoble, June 2003. [bib, pdf]Le travail présenté dans ce rapport a pour objectif de contribuer au domaine de la présentation de documents multimédia. Nous nous intéressons tout particulièrement aux problèmes de conception des formateurs XML. En considérant le problème de la composition des formateurs, nous initialisons une nouvelle direction de recherche sur la conception des formateurs XML par composition. La complexité croissante des documents multimédia, la multiplication des environnements d’exécution et la diversification des attentes des utilisateurs et des auteurs de ces documents ont conduit a l’émergence de nombreux langages de présentation et d’outils de formatage associés (CSS, SVG, SMIL, XSL-FO). Malgré cette évolution vers des systèmes plus puissants et plus performants, les langages comme leurs formateurs sont restés très influencés par les méthodes de formatage de texte. Ils restent très rigides dans leur fonctionnement et donnent peu de solutions face aux nouveaux besoins actuels des documents multimédia. Depuis quelques temps, la communauté de recherche tente de combler ce fossé et a proposé, parmi d’autres, d’utiliser de nouvelles techniques à base de contraintes pour permettre d’étendre l’expressivité des langages de présentation. Cette approche offre une amélioration très intéressante du pouvoir d’expression offert aux auteurs mais les formateurs associés deviennent de plus en plus complexes et difficiles à mettre en oeuvre, et donc à étendre dans le futur. Dans ce stage, nous proposons une architecture logicielle pour un système de présentation multimédia qui permet le couplage d’un langage de présentation et des services de formatage associés avec des systèmes de formatage existants de langage standard comme SMIL ou XSL-FO. Nous voulons non seulement être capable d’intégrer ce langage dans les langages existants mais également de proposer des services de formatage visant à intégrer son traitement dans les formateurs existants. Dans ce cas, le formateur est obtenu par composition (assemblage) des formateurs des langages existants. Donc, Notre ambition est double : intégration des langages et intégration des traitements. Le but est de permettre une meilleure réutilisation des capacités de contrôle offertes par ces langages ainsi que de leurs formateurs. - Langages de transformation
incrémentaux.
Pierre Genevès.
Masters thesis, UJF, Grenoble, June 2003. [bib, pdf]Recently, XML has brought a standard way to exchange structured data between applications. XML transformation is currently considered as a fundamental operation in the data processing sequence of structured data. XML transformation focuses on producing a target XML document from a source XML document with a different structure. A few XML transformation languages have been proposed. These languages were all created with a batch approach, where the full input document is transformed at once. The main limit of this approach is that once a large document has been transformed, when it is modified, a full transformation must be performed again in order to get the new target document. Another approach, called incremental transformation, consists in reflecting the changes of the source document to the target document in an optimal way, i.e. without performing again the full transformation since it has already been done before for a similar source document. This approach makes it possible to create dynamic applications based on the update of the target document. Incremental processing has been studied in many and various research areas, mainly in order to do optimization. We make a synthesis of the main methods successfully developed for incremental processing. This study leads to conditions that make a transformation model suitable for incremental transformation. We then propose a new transformation model based on a rewriting system. Our model is well suited for incremental processing of insertions of structured data in the source document. - Editing SMIL with Timelines.
Cécile Roisin, Vincent Kober, Vincent Quint, Pierre Genevès, Patrice Navarro.
In Proceedings of the Synchronized Multimedia Integration Language European Conference, February 2003. [bib, pdf]This paper presents a timeline approach to editing two of the main components of SMIL: the time and synchronization model and the animation model. This approach is illustrated with two prototypes: the LimSee tool for editing SMIL time structures, and the SVG Animation component included in the Amaya Web client. The timeline view is a faithful representation of the temporal behavior of the document where the author can perform all editing operations related to animation or synchronization between media. The advantages of this authoring approach are shown through editing session excerpts performed with LimSee and the Amaya Animation module. - SMIL Content Adaptation for Embedded
Devices.
Tayeb Lemlouma, Nabil Layaïda.
In Proceedings of the Synchronized Multimedia Integration Language European Conference, February 2003. [bib, pdf]In this paper, we propose a SMIL content adaptation framework for embedded devices such as PDA, cellular phones, etc. This framework is based on a three-pier organization of the SMIL content access which allows decoupling two levels of performance: a wired network with abundant resources such as bandwidth and processing power and, a wireless network with variable bandwidth and limited resources. Clients are given access to content from a variety of terminals with different capabilities. In order to adapt the SMIL content to these devices, the content access traverses an intermediate entity called adaptation proxy where the adaptation occurs. An experimental implementation of this framework shows how to achieve SMIL content adaptation using client profiles descriptions, negotiation strategies, simple SMIL adaptation and media transcoding. - Modélisation et traitement du
contenu des médias pour l’édition et la présentation de documents
multimédia.
Tien Tran-Thuong.
Ph.D. thesis, INPG, Grenoble, February 2003. [bib, pdf]This work proposes a new way to edit/present easily multimedia documents. It consists in modelling the contents of complex media (video, audio) as a structure of sub-elements (moving objects, shots, scenes). These internal media fragments can be associated with behaviors (hyperlinks) or spatial/temporal relations with other objects of the document. This enables richer multimedia presentations thanks to a finer synchronization between media. The difficulty of this work is to insure that this model remains consistent with the composition model of multimedia documents and that it covers the needs of the authors for multimedia fine-grained synchronization. The approach chosen consists in using description tools from MPEG-7 to describe media contents and in integrating these descriptions into an extension of the Madeus constraint-based composition model. - Adapted Content Delivery for
Different Contexts.
Tayeb Lemlouma, Nabil Layaïda.
In Proc. International Symposium on Applications and the Internet (SAINT 2003), pp. 190-197, IEEE Computer Society, January 2003. [bib, pdf]In this paper, we present a framework which allows adapted content delivery for different target contexts. This framework is based on a Universal Profiling Schema UPS for describing the environment characteristics and on an profile exchange protocol. In the server and the proxy side, we give a strategy for matching the different constraints (clients, servers, content, etc.) in order to find an agreement between the server adaptation capabilities and the client preferences and constraints. Usually such environments are subject to frequent changes. To tackle this difficulty, we propose a dynamic adaptation approach based on XSLT for structural transformation and resource aware transcoders for the media adaptation.