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 languages

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 : oai:arXiv.org:1109.5851
    Volume: Volume 7, Issue 4
    Published on: November 22, 2011
    Accepted on: June 25, 2015
    Submitted on: November 24, 2009
    Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3
    Licence: arXiv.org - Non-exclusive license to distribute

    Linked data

    Source : ScholeXplorer References DOI 10.1016/j.disc.2004.04.027
    • 10.1016/j.disc.2004.04.027
    • 10.1016/j.disc.2004.04.027
    Expressive power of existential first-order sentences of Büchi's sequential calculus
    Jean-Eric Pin ;

    2 Documents citing this article

    Export

    BibTeX TEI DC OpenAIRE Crossref DOAJ zbJATS JSON

    Share

    Consultation statistics

    This page has been seen 331 times.
    This article's PDF has been downloaded 368 times.