Definable relations and first-order query languages over strings
From MaRDI portal
Publication:3452507
DOI10.1145/876638.876642zbMath1325.03031OpenAlexW2020437202MaRDI QIDQ3452507
Thomas Schwentick, Michael Benedikt, Luc Segoufin, Leonid O. Libkin
Publication date: 12 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-02796572/file/journal.pdf
Database theory (68P15) Formal languages and automata (68Q45) Logic in computer science (03B70) Quantifier elimination, model completeness, and related topics (03C10) Descriptive complexity and finite models (68Q19)
Related Items (14)
The decision problem for some logics for finite words on infinite alphabets ⋮ Regular model checking revisited ⋮ The past and future of embedded finite model theory ⋮ Synchronizing relations on words ⋮ Regular languages of nested words: fixed points, automata, and synchronization ⋮ First-order and counting theories ofω-automatic structures ⋮ On the expressiveness of Büchi arithmetic ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ Unnamed Item ⋮ Document Spanners ⋮ Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. ⋮ Graph Logics with Rational Relations ⋮ The Quantifier Alternation Hierarchy of Synchronous Relations ⋮ Automatic structures of bounded degree revisited
This page was built for publication: Definable relations and first-order query languages over strings
