Search

• < Previous
• 1
• Next >

---

Graph Logics with Rational Relations

Pablo Barcelo ; Diego Figueira ; Leonid Libkin.

We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topology, which have recently found numerous applications. Such logics use conditions on paths expressed by regular languages&nbsp;[&hellip;]

---

Logics for Unranked Trees: An Overview

Leonid Libkin.

Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extracting data, some for expressing navigational properties, and some make it easy to&nbsp;[&hellip;]

---

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;]

---

Order-Invariant Types and Their Applications

Pablo Barcelo ; Leonid Libkin.

Our goal is to show that the standard model-theoretic concept of types can be applied in the study of order-invariant properties, i.e., properties definable in a logic in the presence of an auxiliary order relation, but not actually dependent on that order relation. This is somewhat surprising since&nbsp;[&hellip;]

---