World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.


    We define tree automata with global equality and disequality constraints (TAGED). TAGEDs can test (dis)equalities between subtrees which may be arbitrarily faraway. In particular, they are equipped with an equality relation and a disequality relation on states, so that whenever two subtrees t and t′ evaluate (in an accepting run) to two states which are in the (dis)equality relation, they must be (dis)equal. We study several properties of TAGEDs, and prove emptiness decidability of for several expressive subclasses of TAGEDs.

    AMSC: 68Q45, 68Q68


    • A. Aiken, D. Kozen and E. L. Wimmers, Information and Computation 122(1), 30 (1995), DOI: 10.1006/inco.1995.1139. Crossref, Web of ScienceGoogle Scholar
    • S. Anantharaman, P. Narendran and M. Rusinowitch, Information Processing Letters 94(5), 231 (2005), DOI: 10.1016/j.ipl.2005.02.004. Crossref, Web of ScienceGoogle Scholar
    • L.   Barguñó et al. , The emptiness problem for tree automata with global constraints , IEEE Symposium on Logic in Computer Science (LICS) . Google Scholar
    • B. Bogaert and S. Tison. Equality and disequality constraints on direct subterms in tree automata. In 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 577 of LNCS, pages 161–171, 1992 . Google Scholar
    • L. Cardelli and G. Ghelli, Mathematical Structures in Computer Science 14, 285 (2004), DOI: 10.1017/S0960129504004141. Crossref, Web of ScienceGoogle Scholar
    • W. Charatonik. Automata on dag representations of finite trees. Technical report, 1999 . Google Scholar
    • W.   Charatonik and L.   Pacholski , Set constraints with projections are in NEXPTIME , IEEE Symposium on Foundations of Computer Science (FOCS) . Google Scholar
    • H. Comon and V. Cortier, Theoretical Computer Science (TCS) 331(1), 143 (2005), DOI: 10.1016/j.tcs.2004.09.036. Crossref, Web of ScienceGoogle Scholar
    • H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: 2007 , . Google Scholar
    • M. Dauchet, A.-C. Caron and J.-L. Coquidé, Journal of Symbolic Computation (JSC) 20, 215 (1995), DOI: 10.1006/jsco.1995.1048. Crossref, Web of ScienceGoogle Scholar
    • E. Filiot. Logics for n-ary queries in trees. PhD thesis, Lille 1 University, 2008 . Google Scholar
    • E. Filiot, J.-M. Talbot and S. Tison, Satisfiability of a spatial logic with tree variables, Computer Science Logic (CSL) (2007) pp. 130–145. Google Scholar
    • E.   Filiot , J.-M.   Talbot and S.   Tison , Tree automata with global constraints , 12th International Conference on Developments in Language Theory (DLT) , Lecture Notes in Computer Science ( Springer Verlag , 2008 ) . Google Scholar
    • R. Gilleron, S. Tison and M. Tommasi, Some new decidability results on positive and negative set constraints, Proceedings of the First International Conference on Constraints in Computational Logics (CCL) (1994) pp. 336–351. Google Scholar
    • V. Halava, M. Hirvensalo and R. de Wolf, Theoretical Computer Science (TCS) 255(1-2), 193 (2001), DOI: 10.1016/S0304-3975(99)00163-2. Crossref, Web of ScienceGoogle Scholar
    • F. Jacquemard, F. Klay and C. Vacher, Rigid tree automata, Proceedings of the 3rd International Conference on Language and Automata Theory and Applications (LATA'09)5457 (Springer, 2009) pp. 446–457. Google Scholar
    • F. Jacquemard, M. Rusinowitch and L. Vigneron, Journal of Logic and Algebraic Programming 75(2), 182 (2008). Crossref, Web of ScienceGoogle Scholar
    • W. Karianto and C. Löding, Unranked tree automata with sibling equalities and disequalities, International Colloquium on Automata Languages and Programming (ICALP)4596 (Springer, 2007) pp. 875–887. Google Scholar
    • J. Mongy. Transformation de noyaux reconnaissables d'arbres. Forêts RATEG. PhD thesis, Université de Lille, 1981 . Google Scholar
    • F. Neven and T. Schwentick, Xpath containment in the presence of disjunction, dtds, and variables, International Conference on Database Theory (ICDT) (Springer-Verlag, London, UK, 2002) pp. 315–329. Google Scholar
    • T. Schwentick, Journal Computer and System Science (JCSS) 73(3), 289 (2007), DOI: 10.1016/j.jcss.2006.10.003. Crossref, Web of ScienceGoogle Scholar
    • K.   Stefansson , Systems of set constraints with negative constraints are nexptime-complete , IEEE Symposium on Logic in Computer Science (LICS) . Google Scholar
    • J. W. Thatcher and J. B. Wright, Mathematical Systems Theory (MST) 2(1), 57 (1968), DOI: 10.1007/BF01691346. Crossref, Web of ScienceGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science