Comparing the succinctness of monadic query languages over finite trees

Martin Grohe; Nicole Schweikardt

The search session has expired. Please query the service again.

Displaying similar documents to “Comparing the succinctness of monadic query languages over finite trees”

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...

Deciding inclusion of set constants over infinite non-strict data structures

Manfred Schmidt-Schauss, David Sabel, Marko Schütz (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

Various static analyses of functional programming languages that permit infinite data structures make use of set constants like , , and , denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. ...

Can we transform logic programs into attribute grammars ?

T. Isakowitz (1991)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The first-order theory of ordering constraints over feature trees.

Müller, Martin, Niehren, Joachim, Treinen, Ralf (2001)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

Nested Sibling Tree Automata

Françoise Gire, Jean-Marc Talbot (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

In the XML standard, data are represented as unranked labeled ordered trees. Regular unranked tree automata provide a useful formalism for the validation of schemas enforcing regular structural constraints on XML documents. However some concrete application contexts need the expression of more general constraints than the regular ones. In this paper we propose a new framework in which context-free style structural constraints can be expressed and validated. This framework is characterized...

Representation of metamorphosis grammar in logic grammar: Proof trees and their lengths.

Prešić, Marica D. (1994)

Publications de l'Institut Mathématique. Nouvelle Série

Similarity:

Learning tree languages from text

Henning Fernau (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the problem of learning regular tree languages from text. We show that the framework of function distinguishability, as introduced by the author in [ (2003) 1679–1711], can be generalized from the case of string languages towards tree languages. This provides a large source of identifiable classes of regular tree languages. Each of these classes can be characterized in various ways. Moreover, we present a generic inference algorithm with polynomial update...

A reduction-based theorem prover for 3-valued logic.

Gabriel Aguilera Venegas, Inmaculada Pérez de Guzmán, Manuel Ojeda Aciego (1997)

Mathware and Soft Computing

Similarity:

We present a new prover for propositional 3-valued logics, TAS-M3, which is an extension of the TAS-D prover for classical propositional logic. TAS-M3 uses the TAS methodology and, consequently, it is a reduction-based method. Thus, its power is based on the reductions of the size of the formula executed by the F transformation. This transformation dynamically filters the information contained in the syntactic structure of the formula to avoid as much distributions as possible, in order...

Rational tree relations.

Raoult, Jean-Claude (1997)

Bulletin of the Belgian Mathematical Society - Simon Stevin

Similarity:

The $μ$ -calculus alternation-depth hierarchy is strict on binary trees

André Arnold (1999)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity: