Search

• < Previous
• 1
• Next >

---

First-Order and Temporal Logics for Nested Words

Rajeev Alur ; Marcelo Arenas ; Pablo Barcelo ; Kousha Etessami ; Neil Immerman ; Leonid Libkin.

Nested words are a structured model of execution paths in procedural programs, reflecting their call and return nesting structure. Finite nested words also capture the structure of parse trees and other tree-structured data, such as XML. We provide new temporal logics for finite and infinite nested&nbsp;[&hellip;]

---

Composition with Target Constraints

Marcelo Arenas ; Ronald Fagin ; Alan Nash.

It is known that the composition of schema mappings, each specified by source-to-target tgds (st-tgds), can be specified by a second-order tgd (SO tgd). We consider the question of what happens when target constraints are allowed. Specifically, we consider the question of specifying the composition&nbsp;[&hellip;]

---

Descriptive Complexity for Counting Complexity Classes

Marcelo Arenas ; Martin Muñoz ; Cristian Riveros.

Descriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive complexity for counting complexity classes, such as FP and #P, has not been systematically studied, and it is not as&nbsp;[&hellip;]

---