Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
3 results

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;]
Published on February 10, 2020
Volume 16, Issue 1

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;]
Published on November 25, 2008
Volume 4, Issue 4

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;]
Published on September 8, 2011
Volume 7, Issue 3
  • < Previous
  • 1
  • Next >