5 papers
Revisiting the Expressiveness Landscape of Data Graph Queries
Michael Benedikt, Anthony Widjaja Lin, Di-De Yen
The study of graph queries in database theory has spanned more than three decades, resulting in a multitude of proposals for graph query languages. We can identify three main famil…
The Counting Power of Transformers
Marco Sälzer, Chris Köcher, Alexander Kozachinskiy +2
Counting properties (e.g. determining whether certain tokens occur more than other tokens in a given input text) have played a significant role in the study of expressiveness of tr…
Answering Constraint Path Queries over Graphs
Heyang Li, Anthony Widjaja Lin, Domagoj VrgoÄ
Constraints are powerful declarative constructs that allow users to conveniently restrict variable values that potentially range over an infinite domain. In this paper, we propose…
Complexity of Evaluating GQL Queries
Diego Figueira, Anthony W. Lin, Liat Peterfreund
GQL has recently emerged as the standard query language over graph databases (particularly, the property graph model). Indeed, this is analogous to the role of SQL for relational d…
The Role of Logic and Automata in Understanding Transformers
Anthony W. Lin, Pablo Barcelo
The advent of transformers has in recent years led to powerful and revolutionary Large Language Models (LLMs). Despite this, our understanding on the capability of transformers is…