16 results on '"Neven, Frank"'
Search Results
2. Expressiveness and complexity of XML publishing transducers
- Author
-
Fan, Wenfei, Geerts, Floris, and Neven, Frank
- Subjects
Electronic publication ,Electronic publishing ,XML ,Electronic publishing -- Analysis ,Transducers -- Analysis ,XML (Document markup language) -- Usage - Abstract
A number of languages have been developed for specifying XML publishing, that is, transformations of relational data into XML trees. These languages generally describe the behaviors of a middleware controller that builds an output tree iteratively, issuing queries to a relational source and expanding the tree with the query results at each step. To study the complexity and expressive power of XML publishing languages, this article proposes a notion of publishing transducers, which generate XML trees from relational data. We study a variety of publishing transducers based on what relational queries a transducer can issue, what temporary stores a transducer can use during tree generation, and whether or not some tree nodes are allowed to be virtual, that is, excluded from the output tree. We first show how existing XML publishing languages can be characterized by such transducers, and thus provide a synergy between theory and practice. We then study the membership, emptiness, and equivalence problems for various classes of transducers. We establish lower and upper bounds, all matching, ranging from PRIME to undecidable. Finally, we investigate the expressive power of these transducers and existing languages. We show that when treated as relational query languages, different classes of transducers capture either complexity classes (e.g., PSPACE) or fragments of datalog (e.g., linear datalog). For tree generation, we establish connections between publishing transducers and logical transductions, among other things. Categories and Subject Descriptors: H.2.5 [Database Management]: Heterogeneous Databases--Data translation; H.1.m [Models and Principles]: Miscellaneous General Terms: Design, Languages, Theory
- Published
- 2008
3. Expressiveness and complexity of XML Schema
- Author
-
Martens, Wim, Neven, Frank, Schwentick, Thomas, and Bex, Geert Jan
- Subjects
XML ,Algorithm ,XML (Document markup language) -- Analysis ,Algorithms -- Analysis - Abstract
The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical characterizations of the Element Declarations Consistent (EDC) rule are provided. In particular, it is obtained that schemas satisfying EDC can only reason about regular properties of ancestors of nodes. Hence, with respect to expressive power, XML Schema is closer to DTDs than to tree automata. These theoretical results are complemented with an investigation of the XML Schema Definitions (XSDs) occurring in practice, revealing that the extra expressiveness of XSDs over DTDs is only used to a very limited extent. As this might be due to the complexity of the XML Schema specification and the difficulty of understanding the effect of constraints on typing and validation of schemas, a simpler formalism equivalent to XSDs is proposed. It is based on contextual patterns rather than on recursive types and it might serve as a light-weight front end for XML Schema. Next, the effect of EDC on the way XML documents can be typed is discussed. It is argued that a cleaner, more robust, larger but equally feasible class is obtained by replacing EDC with the notion of 1-pass preorder typing (1PPT): schemas that allow one to determine the type of an element of a streaming document when its opening tag is met. This notion can be defined in terms of grammars with restrained competition regular expressions and there is again an equivalent syntactical formalism based on contextual patterns. Finally, algorithms for recognition, simplification, and inclusion of schemas for the various classes are given. Categories and Subject Descriptors: H.2.1 [Database Management]: Logical Design; F.4.3 [Mathematical Logic and Formal Languages]: Formal Languages General Terms: Algorithms, Design, Languages, Standardization, Theory Additional Key Words and Phrases: XML, XML Schema, validation
- Published
- 2006
4. 05061 Abstracts Collection ��� Foundations of Semistructured Data
- Author
-
Neven, Frank, Schwentick, Thomas, and Suciu, Dan
- Subjects
database theory ,XML ,document processing ,Semistructured data - Abstract
From 06.02.05 to 11.02.05, the Dagstuhl Seminar 05061 ``Foundations of Semistructured Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
- Published
- 2005
- Full Text
- View/download PDF
5. Inference of Concise Regular Expressions and DTDs.
- Author
-
Bex, Geert Jan, Neven, Frank, Schwentick, Thomas, and Vansummeren, Stijn
- Subjects
- *
DOCUMENT type definitions , *XML (Extensible Markup Language) , *WEB services , *DATA , *COMPUTER networks , *ALGORITHMS , *THEORY - Abstract
We consider the problem of inferring a concise Document Type Definition (DTD) for a given set of XML-documents, a problem that basically reduces to learning concise regular expressions from positive examples strings.We identify two classes of concise regular expressions-the single occurrence regular expressions (SOREs) and the chain regular expressions (CHAREs)-that capture the far majority of expressions used in practical DTDs. For the inference of SOREs we present several algorithms that first infer an automaton for a given set of example strings and then translate that automaton to a corresponding SORE, possibly repairing the automaton when no equivalent SORE can be found. In the process, we introduce a novel automaton to regular expression rewrite technique which is of independent interest. When only a very small amount of XML data is available, however (for instance when the data is generated by Web service requests or by answers to queries), these algorithms produce regular expressions that are too specific. Therefore, we introduce a novel learning algorithm CRX that directly infers CHAREs (which form a subclass of SOREs) without going through an automaton representation.We show that CRX performs very well within its target class on very small datasets. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
6. Typechecking top-down XML transformations: Fixed input or output schemas
- Author
-
Martens, Wim, Neven, Frank, and Gyssens, Marc
- Subjects
- *
MACHINE theory , *ELECTROMECHANICAL devices , *XML (Extensible Markup Language) , *ELECTRONIC data processing - Abstract
Abstract: Typechecking consists of statically verifying whether the output of an XML transformation always conforms to an output type for documents satisfying a given input type. In this general setting, both the input and output schema as well as the transformation are part of the input for the problem. However, scenarios where the input or output schema can be considered to be fixed, are quite common in practice. In the present work, we investigate the computational complexity of the typechecking problem in the latter setting. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
7. Frontiers of tractability for typechecking simple XML transformations
- Author
-
Martens, Wim and Neven, Frank
- Subjects
- *
XML (Extensible Markup Language) , *ELECTROMECHANICAL devices , *ALGORITHMS , *MACHINE theory - Abstract
Abstract: Typechecking consists of statically verifying whether the output of an XML transformation is always conform to an output type for documents satisfying a given input type. We focus on complete algorithms which always produce the correct answer. We consider top–down XML transformations incorporating XPath expressions and abstract document types by grammars and tree automata. By restricting schema languages and transformations, we identify several practical settings for which typechecking can be done in polynomial time. Moreover, the resulting framework provides a rather complete picture as we show that most scenarios cannot be enlarged without rendering the typechecking problem intractable. So, the present research sheds light on when to use fast complete algorithms and when to reside to sound but incomplete ones. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
8. On the complexity of typechecking top-down XML transformations
- Author
-
Martens, Wim and Neven, Frank
- Subjects
- *
XML (Extensible Markup Language) , *DOCUMENT markup languages , *ELECTROMECHANICAL devices , *QUERY languages (Computer science) - Abstract
Abstract: We investigate the typechecking problem for XML transformations: statically verifying that every answer to a transformation conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as input and output schemas. The complexity of the typechecking problems in this scenario ranges from to . [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
9. Attribute grammars for unranked trees as a query language for structured documents
- Author
-
Neven, Frank
- Subjects
- *
GRAMMAR , *MATHEMATICAL analysis , *XML (Extensible Markup Language) , *QUERY languages (Computer science) - Abstract
Abstract: Document specification languages, like for instance XML, model documents using extended context-free grammars. These differ from standard context-free grammars in that they allow arbitrary regular expressions on the right-hand side of productions. To query such documents, we introduce a new form of attribute grammars (extended AGs) that work directly over extended context-free grammars rather than over standard context-free grammars. Viewed as a query language, extended AGs are particularly relevant as they can take into account the inherent order of the children of a node in a document. We show that non-circularity remains decidable in EXPTIME and establish the complexity of the non-emptiness and equivalence problem of extended AGs to be complete for EXPTIME. As an application we show that the Region Algebra expressions can be efficiently translated into extended AGs. This translation drastically improves the known upper bound on the complexity of the emptiness and equivalence test for Region Algebra expressions from non-elementary to EXPTIME. Finally, we characterize the expressiveness of extended AGs in terms of monadic second-order logic. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
10. Finite state machines for strings over infinite alphabets.
- Author
-
Neven, Frank, Schwentick, Thomas, and Vianu, Victor
- Abstract
Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics defining the regular languages on finite alphabets. Specifically, we consider register and pebble automata, and extensions of first-order logic and monadic second-order logic. For each type of automaton we consider one-way and two-way variants, as well as deterministic, nondeterministic, and alternating control. We investigate the expressiveness and complexity of the automata and their connection to the logics, as well as standard decision problems. Some of our results answer open questions of Kaminski and Francez on register automata. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
11. Query automata over finite trees
- Author
-
Neven, Frank and Schwentick, Thomas
- Subjects
- *
COMPUTER programming , *ELECTRONIC data processing - Abstract
A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an important role in the context of structured document databases. The motivation of this work is to understand how the natural and well-studied computation model of tree automata can be used to compute such queries. We define a query automaton (QA) as a deterministic two-way finite automaton over trees that has the ability to select nodes depending on the state and the label at those nodes. We study QAs over ranked as well as over unranked trees. Unranked trees differ from ranked ones in that there is no bound on the number of children of nodes. We characterize the expressiveness of the different formalisms as the unary queries definable in monadic second-order logic (MSO). In contrast to the ranked case, special stay transitions had to be added to QAs over unranked trees to capture MSO. We establish the complexity of the non-emptiness, containment, and equivalence of QAs to be complete for EXPTIME. [Copyright &y& Elsevier]
- Published
- 2002
- Full Text
- View/download PDF
12. A formal model for an expressive fragment of XSLT
- Author
-
Bex, Geert Jan, Maneth, Sebastian, and Neven, Frank
- Subjects
- *
XSLT (Computer program language) , *QUERY languages (Computer science) - Abstract
The extension of the eXtensible Style sheet Language (XSL) by variables and passing of data values between template rules has generated a powerful XML query language: eXtensible Style sheet Language Transformations (XSLT). An informal introduction to XSTL is given, on the bases of which a formal model of a fragment of XSLT is defined. This formal model is in the spirit of tree transducers, and its semantics is defined by rewrite relations. It is shown that the expressive power of the fragment is already beyond that of most other XML query languages. Finally, important properties such as termination and closure under composition are considered. [Copyright &y& Elsevier]
- Published
- 2002
- Full Text
- View/download PDF
13. Simplifying XML Schema: Single-type approximations of regular tree languages.
- Author
-
Gelade, Wouter, Idziaszek, Tomasz, Martens, Wim, Neven, Frank, and Paredaens, Jan
- Subjects
- *
XML (Extensible Markup Language) , *SCHEME programming language , *APPROXIMATION theory , *REGULAR graphs , *TREE graphs , *PROGRAMMING languages - Abstract
Abstract: XML Schema Definitions (XSDs) can be adequately abstracted by the single-type regular tree languages. It is well known that these form a strict subclass of the robust class of regular unranked tree languages. Sadly, in this respect, XSDs are not closed under the basic operations of union and set difference, complicating important tasks in schema integration and evolution. The purpose of this paper is to investigate how the union and difference of two XSDs can be approximated within the framework of single-type regular tree languages. We consider both optimal lower and upper approximations. We also address the more general question of how to approximate an arbitrary regular tree language by an XSD and consider the complexity of associated decision problems. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
14. BonXai
- Author
-
Frank Neven, Thomas Schwentick, Wim Martens, Matthias Niewerth, MARTENS, Wim, NEVEN, Frank, Niewerth, Matthias, and Schwentick, Thomas
- Subjects
Document Structure Description ,XML Encryption ,Schematron ,Computer science ,computer.internet_protocol ,Efficient XML Interchange ,XML ,BonXai ,XML Schema ,schema languages ,XML Signature ,02 engineering and technology ,computer.software_genre ,Logical schema ,XML Schema Editor ,020204 information systems ,Schema (psychology) ,Streaming XML ,0202 electrical engineering, electronic engineering, information engineering ,RELAX NG ,XML schema ,computer.programming_language ,Programming language ,cXML ,XML validation ,computer.file_format ,XML framework ,XML database ,XML Schema (W3C) ,Document Schema Definition Languages ,Star schema ,Document Definition Markup Language ,ComputingMethodologies_DOCUMENTANDTEXTPROCESSING ,020201 artificial intelligence & image processing ,Data mining ,computer ,Information Systems - Abstract
While the migration from DTD to XML Schema was driven by a need for increased expressivity and flexibility, the latter was also significantly more complex to use and understand. Whereas DTDs are characterized by their simplicity, XML Schema Documents are notoriously difficult. In this article, we introduce the XML specification language BonXai, which incorporates many features of XML Schema but is arguably almost as easy to use as DTDs. In brief, the latter is achieved by sacrificing the explicit use of types in favor of simple patterns expressing contexts for elements. The goal of BonXai is not to replace XML Schema but rather to provide a simpler alternative for users who want to go beyond the expressiveness and features of DTD but do not need the explicit use of types. Furthermore, XML Schema processing tools can be used as a back-end for BonXai, since BonXai can be automatically converted into XML Schema. A particularly strong point of BonXai is its solid foundation rooted in a decade of theoretical work around pattern-based schemas. We present a formal model for a core fragment of BonXai and the translation algorithms to and from a core fragment of XML Schema. We prove that BonXai and XML Schema can be converted back-and-forth on the level of tree languages and we formally study the size trade-offs between the two languages. We acknowledge the financial support of grant number MA 4938/2-1 from the Deutsche Forschungsgemeinschaft (Emmy Noether Nachwuchsgruppe). We further acknowledge the financial support of the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under the FET-Open grant agreement FOX, number FP7-ICT-233599.
- Published
- 2017
15. Typechecking top-down XML transformations: Fixed input or output schemas
- Author
-
Frank Neven, Wim Martens, Marc Gyssens, MARTENS, Wim, NEVEN, Frank, and GYSSENS, Marc
- Subjects
Input/output ,Theoretical computer science ,Computational complexity theory ,Programming language ,computer.internet_protocol ,Complexity ,Top-down and bottom-up design ,XSLT ,XML ,Typechecking ,computer.software_genre ,Computer Science Applications ,Theoretical Computer Science ,Tree transformations ,tree transformations ,typechecking ,unranked tree transducers ,complexity ,Computational Theory and Mathematics ,Schema (psychology) ,Unranked tree transducers ,computer ,Information Systems ,computer.programming_language ,Mathematics - Abstract
Typechecking consists of statically verifying whether the output of an XML transformation always conforms to an output type for documents satisfying a given input type. In this general setting, both the input and output schema as well as the transformation are part of the input for the problem. However, scenarios where the input or output schema can be considered to be fixed, are quite common in practice. In the present work, we investigate the computational complexity of the typechecking problem in the latter setting. (c) 2008 Elsevier Inc. All rights reserved.
- Published
- 2008
16. Visibly Pushdown Transducers
- Author
-
Servais, Frédéric, Alur, Rajeev, Filiot, Emmanuel, Raskin, Jean-François, Maneth, Sebastian, Neven, Frank, Vansummeren, Stijn, and Zimanyi, Esteban
- Subjects
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES ,Informatique générale ,Transducers ,Langages formels ,XML ,Sciences de l'ingénieur ,nested words ,Transducteurs ,Formal languages ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Formal Language ,XML (Document markup language) ,XML (Langage de balisage) ,Visibly pushdown automata ,Computer Science::Formal Languages and Automata Theory - Abstract
The present work proposes visibly pushdown transducers (VPTs) for defining transformations of documents with a nesting structure. We show that this subclass of pushdown transducers enjoy good properties. Notably, we show that functionality is decidable in PTime and k-valuedness in co-NPTime. While this class is not closed under composition and its type checking problem against visibly pushdown automata is undecidable, we identify a subclass, the well-nested VPTs, closed under composition and with a decidable type checking problem. Furthermore, we show that the class of VPTs is closed under look-ahead, and that the deterministic VPTs with look-ahead characterize the functional VPTs transductions. Finally, we investigate the resources necessary to perform transformations defined by VPTs. We devise a memory efficient algorithm. Then we show that it is decidable whether a VPT transduction can be performed with a memory that depends on the level of nesting of the input document but not on its length., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished
- Published
- 2011
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.