Alonzo Church Award for VCLA board members Georg Gottlob and Reinhard Pichler
The winners of the Alonzo Church Award 2021: Georg Gottlob, Christoph Koch, Reinhard Pichler, Klaus U. Schulz and Luc Segoufin
Alonzo Church Award 2021 Winners
The ACM Special Interest Group for Logic and Computation (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Gödel Society (KGS) have announced that:
Georg Gottlob (VCLA advisory board member), Christoph Koch, Reinhard Pichler (VCLA executive board member), Klaus U. Schulz, and Luc Segoufin
have been selected as the winners of the prestigious 2021 Alonzo Church Award for Outstanding Contributions to Logic and Computation.
They are awarded for their fundamental work on logic-based web data extraction and querying tree-structured data,
published in:
(1) Georg Gottlob and Christoph Koch. “Monadic Datalog and the Expressive Power of Languages for Web Information Extraction.” Journal of the ACM (JACM) 51.1 (2004): 74-113.
(2) Georg Gottlob, Christoph Koch, and Klaus U. Schulz. “Conjunctive Queries Over Trees.” Journal of the ACM (JACM) 53.2 (2006): 238-272.
(3) Georg Gottlob, Christoph Koch, and Reinhard Pichler. “Efficient Algorithms for Processing XPath Queries.” ACM Transactions on Database Systems (TODS) 30.2 (2005): 444-491.
(4) Georg Gottlob, Christoph Koch, Reinhard Pichler, and Luc Segoufin. “The Complexity of XPath Query Evaluation and XML Typing.” Journal of the ACM (JACM) 52.2 (2005): 284-335.
The Contribution
Paper (1) establishes a comprehensive logical theory of Web data extraction. At its core, this is the problem of selecting relevant nodes (subtrees) from HTML text. While the set of relevant nodes can be expressed in Monadic Second-Order logic (MSO) over finite trees, MSO has high computationally complexity. The authors prove that Monadic Datalog on trees has exactly the same expressive power as full MSO and that, surprisingly, evaluating Monadic Datalog is feasible in time linear in the size of query and input tree. These results greatly influenced theoretical and applied research, and gave rise to logic-based systems for data extraction that have been successfully used in industry.
Papers (2,3,4) present deep investigations into logical queries over tree-structured
data. The complexity of evaluating XPath, a key technology in Web browsers and other systems, was unclear, and available implementations required exponential time. Paper (2) gives a full characterization of, and a dichotomy theorem for, the complexity of conjunctive queries on various representations of trees. Paper (3) shows that the full XPath standard can be evaluated in PTIME and proposes a logical core which has become seminal to research efforts at the intersection of Web data processing and (modal) logics. Finally, paper (4) establishes the precise complexity of evaluating XPath fragments.
About the Alonzo Church Award
The Alonzo Church Award for Outstanding Contributions to Logic and Computation was established in 2015 by the ACM Special Interest Group for Logic and Computation (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Gödel Society (KGS). The award is for an outstanding contribution represented by a paper or small group of papers within the past 25 years.