Computing thejth solution of a first-order query

DOI10.1051/ita:2007046zbMath1149.68028OpenAlexW2097185467MaRDI QIDQ3514640

Guillaume Bagan, Arnaud Durand, Etienne Grandjean, Frédéric Olive

Publication date: 21 July 2008

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92857

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items

Unnamed Item ⋮ Structural tractability of enumerating CSP solutions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Linear delay enumeration and monadic second-order logic
• On the complexity of database queries
• The complexity of acyclic conjunctive queries
• Deciding first-order properties of locally tree-decomposable structures
• A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
• First-Order Queries over One Unary Function
• Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
• First-order queries on structures of bounded degree are computable with constant delay