Thomas Place ; Luc Segoufin - A decidable characterization of locally testable tree languages

lmcs:1210 - Logical Methods in Computer Science, November 22, 2011, Volume 7, Issue 4 - https://doi.org/10.2168/LMCS-7(4:3)2011
A decidable characterization of locally testable tree languagesArticle

Authors: Thomas Place ; Luc Segoufin

    A regular tree language L is locally testable if membership of a tree in L depends only on the presence or absence of some fix set of neighborhoods in the tree. In this paper we show that it is decidable whether a regular tree language is locally testable. The decidability is shown for ranked trees and for unranked unordered trees.

    https://doi.org/10.2168/LMCS-7(4:3)2011
    Source: arXiv.org:1109.5851
    Volume: Volume 7, Issue 4
    Published on: November 22, 2011
    Imported on: November 24, 2009
    Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3
    Licence: arXiv.org - Non-exclusive license to distribute

    Publications

    References
    Expressive power of existential first-order sentences of Büchi's sequential calculus
    • 1 ScholeXplorer

    References

    Share and export

    Consultation statistics

    This page has been seen 743 times.
    This article's PDF has been downloaded 394 times.