Abstract
There are many decision problems in automata theory (including membership, emptiness, emptiness of intersection, inclusion and universality problems) that for some classes of tree automata are NP-hard. The study of their parameterized complexity allows us to find new bounds of their non-polynomial time algorithmic behaviors. We present results of such a study for classical tree automata (TA), rigid tree automata (RTA), tree automata with global equality and disequality (TAGED) and t-DAG automata.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anantharaman, S., Narendran, P., Rusinowitch, M.: Closure properties and decision problems of dag automata. Inf. Process. Lett. 94(5), 231–240 (2005)
Barecka, A., Charatonik, W.: The parameterized complexity of chosen problems for finite automata on trees (2010), http://www.math.uni.wroc.pl/~barecka/papers/param_aut.pdf
Barguñó, L., Creus, C., Godoy, G., Jacquemard, F., Vacher, C.: The emptiness problem for tree automata with global constraints. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science (LICS 2010), pp. 263–272. IEEE Computer Society Press, Edinburgh (2010)
Charatonik, W.: Automata on DAG representations of finite trees. Technical Report MPI-I-1999-2-001, Max-Planck-Institut für Informatik (1999)
Charatonik, W., Pacholski, L.: Set constraints with projections. Journal of the ACM 57(4), 1–37 (2010)
Comon-Lundh, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (November 2007), http://www.grappa.univ-lille3.fr/tata/
Downey, R.G., Fellows, M.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)
Filiot, E., Talbot, J.M., Tison, S.: Tree automata with global constraints. Int. J. Found. Comput. Sci. 21(4), 571–596 (2010)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag New York, Inc., Secaucus (2006)
Jacquemard, F., Klay, F., Vacher, C.: Rigid tree automata. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 446–457. Springer, Heidelberg (2009)
Lichtenstein, O., Pnueli, A.: Checking that finite state concurrent programs satisfy their linear specification. In: POPL, pp. 97–107 (1985)
Wareham, T.: The parameterized complexity of intersection and composition operations on sets of finite-state automata. In: Yu, S., Păun, A. (eds.) CIAA 2000. LNCS, vol. 2088, pp. 302–310. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barecka, A., Charatonik, W. (2011). The Parameterized Complexity of Chosen Problems for Finite Automata on Trees. In: Dediu, AH., Inenaga, S., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2011. Lecture Notes in Computer Science, vol 6638. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21254-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-21254-3_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21253-6
Online ISBN: 978-3-642-21254-3
eBook Packages: Computer ScienceComputer Science (R0)