Parameterized complexity of basic decision problems for tree automata

References

• Anantharaman , S. , Narendran , P. and Rusinowitch , M. 2005 . Closure properties and decision problems of dag automata . Inf. Process. Lett. , 94 ( 5 ) : 231 – 240 . (doi:10.1016/j.ipl.2005.02.004)
   Web of Science ®Google Scholar
• Barecka , A. and Charatonik , W. The parameterized complexity of chosen problems for finite automata on trees . Proceedings of the 5th International Conference on Language and Automata Theory and Applications (LATA’11), Tarragona . Edited by: Dediu , A. H. , Inenaga , S. and Martín-Vide , C. pp. 129 – 141 . Berlin, Heidelberg : Springer . Lecture Notes in Computer Science, Vol. 6638
   Google Scholar
• Barguñó , L. , Creus , C. , Godoy , G. , Jacquemard , F. and Vacher , C. The emptiness problem for tree automata with global constraints . Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science (LICS’10), Edinburgh . Edited by: Jouannaud , J. P. July . pp. 263 – 272 . Washington : IEEE Computer Society Press .
   Google Scholar
• Charatonik , W. 1999 . “ Automata on DAG representations of finite trees ” . Saarbrucken : Max-Planck-Institut für Informatik . Tech. Rep. MPI-I-1999-2-001
   Google Scholar
• Charatonik , W. and Pacholski , L. 2010 . Set constraints with projections . J. ACM , 57 ( 4 ) : 1 – 37 .
   Google Scholar
• Comon-Lundh , H. , Dauchet , M. , Gilleron , R. , Löding , C. , Jacquemard , F. , Lugiez , D. , Tison , S. and Tommasi , M. November 2007 . Tree Automata Techniques and Applications November , Available at http://www.grappa.univ-lille3.fr/tata/.
   Google Scholar
• Devienne , P. , Talbot , J.-M. and Tison , S. Set-based analysis for logic programming and tree automata . Proceedings of the Static Analysis Symposium (SAS’97), Paris . Edited by: Van Hentenryck , P. pp. 127 – 140 . Berlin, Heidelberg : Springer . Lecture Notes in Computer Science, Vol. 1302
   Google Scholar
• Downey , R. G. and Fellows , M. R. 1999 . Parameterized Complexity , New York : Springer-Verlag . Monographs in Computer Science
   Google Scholar
• Filiot , E. , Talbot , J.-M. and Tison , S. 2010 . Tree automata with global constraints . Int. J. Found. Comput. Sci. , 21 ( 4 ) : 571 – 596 . (doi:10.1142/S012905411000743X)
   Web of Science ®Google Scholar
• Flum , J. and Grohe , M. 2006 . Parameterized Complexity Theory , Secaucus , NJ : Springer-Verlag . Texts in Theoretical Computer Science, EATCS
   Google Scholar
• Hopcroft , J. and Ullman , J. 1979 . Introduction to Automata Theory, Languages, and Computation , Reading , MA : Addison-Wesley .
   Google Scholar
• Jacquemard , F. , Klay , F. and Vacher , C. Rigid tree automata . Proceedings of the 3rd International Conference on Language and Automata Theory and Applications (LATA 09), Tarragona . Edited by: Dediu , A. H. , Ionescu , A. M. and Martín-Vide , C. April . pp. 446 – 457 . Berlin, Heidelberg : Springer . Lecture Notes in Computer Science, Vol. 5457
   Google Scholar
• Lichtenstein , O. and Pnueli , A. Checking that finite state concurrent programs satisfy their linear specification . Proceedings of the 12th ACM Symposium on Principles of Programming Languages (POPL’85), New Orleans . Edited by: Van Deusen , M. S. , Galil , Z. and Reid , B. K. pp. 97 – 107 . New York : ACM .
   Google Scholar
• Lohrey , M. On the parallel complexity of tree automata . Proceedings of the 12th International Conference on Rewrite Techniques and Applications (RTA’01), Utrecht . pp. 201 – 215 . Berlin, Heidelberg : Springer . Lecture Notes in Computer Science, Vol. 2051, A. Middeldorp, ed.
   Google Scholar
• Monniaux , D. 2003 . Abstracting cryptographic protocols with tree automata . Sci. Comput. Program. , 47 ( 2–3 ) : 177 – 202 . (doi:10.1016/S0167-6423(02)00132-6)
   Web of Science ®Google Scholar
• Schwentick , T. 2007 . Automata for XML – a survey . J. Comput. Syst. Sci. , 73 ( 3 ) : 289 – 315 . (doi:10.1016/j.jcss.2006.10.003)
   Web of Science ®Google Scholar
• Wareham , T. The parameterized complexity of intersection and composition operations on sets of finite-state automata . Proceedings of the 5th International Conference on Implementation and Application of Automata (CIAA’01), London, Ontario, Canada . Edited by: Yu , S. and Paun , A. pp. 302 – 310 . Berlin, Heidelberg : Springer . Lecture Notes in Computer Science, Vol. 2088
   Google Scholar