Definable relations and first-order query languages over strings
From MaRDI portal
Publication:3452507
DOI10.1145/876638.876642zbMath1325.03031MaRDI 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
68P15: Database theory
68Q45: Formal languages and automata
03B70: Logic in computer science
03C10: Quantifier elimination, model completeness, and related topics
68Q19: Descriptive complexity and finite models
Related Items
Graph Logics with Rational Relations, First-order and counting theories ofω-automatic structures, Regular languages of nested words: fixed points, automata, and synchronization, The decision problem for some logics for finite words on infinite alphabets, Synchronizing relations on words, Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al., The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata, Document Spanners, Automatic structures of bounded degree revisited