First-Order and Temporal Logics for Nested Words

Rajeev Alur, University of Pennsylvania
Marcelo Arenas, Pontificia Universidad Catolica de Chile
Pablo Barcelo, Universidad de Chile
Kousha Etessami, University of Edinburgh
Neil Immerman, University of Massachusetts
Leonid Libkin, University of Edinburgh

Article comments

Reprinted from:

First-Order and Temporal Logics for Nested Words. Rajeev Alur, Marcelo Arenas, Pablo Barcelo, Kousha Etessami, Neil Immerman, Leonid Libkin. Logical Methods in Computer Science. Vol. 4 (4:11) 2008, pp. 1–44

Abstract

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 words, which are natural extensions of LTL, and prove that these logics are first-order expressively-complete. One of them is based on adding a "within" modality, evaluating a formula on a subword, to a logic CaRet previously studied in the context of verifying properties of recursive state machines (RSMs). The other logic, NWTL, is based on the notion of a summary path that uses both the linear and nesting structures. For NWTL we show that satisfiability is EXPTIME-complete, and that model-checking can be done in time polynomial in the size of the RSM model and exponential in the size of the NWTL formula (and is also EXPTIME-complete). Finally, we prove that first-order logic over nested words has the three-variable property, and we present a temporal logic for nested words which is complete for the two-variable fragment of first-order.