Spanners: A Formal Framework for Information Extraction
Summary: Propose "spanners": functions mapping strings to span-relations, formalizing primitive representations (regex with capture variables and two automata models) and their algebraic closure. Prove one automaton equals regex captures, the other characterizes regular spanners; introduce core spanners with string-equality and show regular spanners closed under difference but core spanners are not. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Ronald Fagin
- 2. Benny Kimelfeld
- 3. Frederick Reiss
- 4. Stijn Vansummeren
Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,045 | Dichotomies in the Complexity of Preferred Repairs | 2015 | PODS | 7.6618214e-05 |
| 5,406 | Cleaning Inconsistencies in Information Extraction via Prioritized Repairs | 2014 | PODS | 5.5239588e-05 |
| 6,345 | A Relational Framework for Classifier Engineering | 2017 | PODS | 5.0970607e-05 |
| 9,429 | Database Principles in Information Extraction | 2014 | PODS | 4.3399748e-05 |
| 12,070 | Next Generation Data Analytics at IBM Research | 2013 | VLDB | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 49 | Consistent Query Answers in Inconsistent Databases | 1999 | PODS | 0.00067607389 |
| 256 | GraphLog: a Visual Formalism for Real Life Recursion | 1990 | PODS | 0.00030241337 |
| 364 | A Graphical Query Language Supporting Recursion | 1987 | SIGMOD | 0.00025657601 |
| 808 | Query Containment for Conjunctive Queries With Regular Expressions | 1998 | PODS | 0.000164132 |
| 6,527 | Automatic Rule Refinement for Information Extraction | 2010 | VLDB | 5.0200332e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,198 | Algebras for Querying Text Regions (Extended Abstract) | 1995 | PODS | 5.6294569e-05 |
| 10,904 | Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FC | 2024 | PODS | 4.1905499e-05 |
| 6,527 | Automatic Rule Refinement for Information Extraction | 2010 | VLDB | 5.0200332e-05 |
| 6,956 | Computational Aspects of Resilient Data Extraction from Semistructured Sources | 2000 | PODS | 4.8811374e-05 |
| 11,242 | Autonomously Computable Information Extraction | 2023 | VLDB | 4.1905499e-05 |
| 8,749 | Document Spanners — A Brief Overview of Concepts, Results, and Recent Developments | 2022 | PODS | 4.4520434e-05 |
| 13,176 | SpannerLib: Embedding Declarative Information Extraction in an Imperative Workflow | 2024 | VLDB | - |
| 5,406 | Cleaning Inconsistencies in Information Extraction via Prioritized Repairs | 2014 | PODS | 5.5239588e-05 |
| 2,932 | Complexity Bounds for Relational Algebra over Document Spanners | 2019 | PODS | 7.8724421e-05 |
| 1,940 | Split-Correctness in Information Extraction | 2019 | PODS | 0.00010019194 |