Displaying similar documents to “Comparing classification tree structures: a special case of comparing q-ary relations ”

Comparing classification tree structures: A special case of comparing -ary relations II

I. C. Lerman, F. Rouxel (2010)

RAIRO - Operations Research

Similarity:

Comparing -ary relations on a set 𝒪 of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to tree comparison are discussed in the...

Coalgebras for Binary Methods: Properties of Bisimulations and Invariants

Hendrik Tews (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Coalgebras for endofunctors 𝒞 𝒞 can be used to model classes of object-oriented languages. However, binary methods do not fit directly into this approach. This paper proposes an extension of the coalgebraic framework, namely the use of 𝒞 o p × 𝒞 𝒞 . This extension allows the incorporation of binary methods into coalgebraic class specifications. The paper also discusses how to define bisimulation and invariants for coalgebras of extended polynomial functors and proves many...

Cutwidth of the -dimensional Mesh of -ary Trees

Imrich Vrťo (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that the cutwidth of the -dimensional mesh of -ary trees is of order Θ ( d ( r - 1 ) n + 1 ) , which improves and generalizes previous results.

Moderate Deviations for I.I.D. Random Variables

Peter Eichelsbacher, Matthias Löwe (2010)

ESAIM: Probability and Statistics

Similarity:

We derive necessary and sufficient conditions for a sum of i.i.d. random variables i = 1 n X i / b n – where b n n 0 , but b n n – to satisfy a moderate deviations principle. Moreover we show that this equivalence is a typical moderate deviations phenomenon. It is not true in a large deviations regime.

On the parameterized complexity of approximate counting

J. Andrés Montoya (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class # W [ P ] , the parameterized analogue of # P . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

On the parameterized complexity of approximate counting

J. Andrés Montoya (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class # W [ P ] , the parameterized analogue of # P . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.