Convergent Sequences of Discrete Structures and Testability / SequÃncias Convergentes de Estruturas Discretas e Testabilidade

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

27/02/2012

RESUMO

In this work, we studied the recent theory of convergent graph sequences and its extensions to permutation and partially ordered sets with fix dimension. Weâve conjectured a lemma of weak regularity on intervals that, if this conjecture is true, we can extend this theory to ordered graphs, which are graphs such that there is a total order on its vertices. We show some interesting relations on permutation and partially ordered sets with ordered graphs. Then, we obtain another proof to the existence of limit objects for all convergent permutation sequences. We also proved that all hereditary property of either permutation or ordered graph is testable.

ASSUNTO(S)

ciencia da computacao teoria dos grafos linguagens formais

Documentos Relacionados