Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/33418
Title: | Spanners: A Formal Framework for Information Extraction | Authors: | Fagin, Ronald Kimelfeld, Benny Reiss, Frederick VANSUMMEREN, Stijn |
Issue Date: | 2013 | Publisher: | Association for Computing Machinery | Source: | Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Association for Computing Machinery, p. 37 -48 | Abstract: | An intrinsic part of information extraction is the creation and manipulation of relations extracted from text. In this paper, we develop a foundational framework where the central construct is what we call a spanner. A spanner maps an input string into relations over the spans (intervals specified by bounding indices) of the string. The focus of this paper is on the representation of spanners. Conceptually , there are two kinds of such representations. Spanners defined in a primitive representation extract relations directly from the input string; those defined in an algebra apply algebraic operations to the primitively represented spanners. This framework is driven by SystemT, an IBM commercial product for text analysis , where the primitive representation is that of regular expressions with capture variables. We define additional types of primitive spanner representations by means of two kinds of automata that assign spans to variables. We prove that the first kind has the same expressive power as regular expressions with capture variables; the second kind expresses precisely the algebra of the regular spanners-the closure of the first kind under standard relational operators. The core spanners extend the regular ones by string-equality selection (an extension used in SystemT). We give some fundamental results on the expressiveness of regular and core spanners. As an example, we prove that regular spanners are closed under difference (and complement), but core spanners are not. Finally, we establish connections with related notions in the literature. | Keywords: | H21 [Database Management]: Logical Design-Data models;H24 [Database Management]: Systems-Textual databases, Re- lational databases, Rule-based databases;I54 [Pattern Recogni- tion]: Applications-Text processing;F43 [Mathematical Logic and Formal Languages]: Formal Languages-Algebraic language theory, Classes defined by grammars or automata, Operations on languages;[ [F]:11]Computation by Abstract DevicesModels of Computation[Automata, Relations between models] Keywords Information extraction, spanners, regular expressions, finite-state automata | Document URI: | http://hdl.handle.net/1942/33418 | ISBN: | 9781450320665 | DOI: | 10.1145/2463664.2463665 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1-aqlf.pdf Restricted Access | Published version | 371.41 kB | Adobe PDF | View/Open Request a copy |
Page view(s)
26
checked on Sep 5, 2022
Download(s)
6
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.