Abstract
We propose an extension of visibly pushdown automata by means of weights (represented as positive integers) associated with transitions, called visibly pushdown automata with multiplicities. The multiplicity of a computation is the product of the multiplicities of the transitions used along this computation. The multiplicity of an input is the sum of the ones of all its successful computations. Finally, the multiplicity of such an automaton is the supremum of multiplicities over all possible inputs.
We prove the problem of deciding whether the multiplicity of an automaton is finite to be in PTime. We also consider the K-boundedness problem, i.e. deciding whether the multiplicity is bounded by K: we prove this problem to be ExpTime-complete when K is part of the input and in PTime when K is fixed.
As visibly pushdown automata are closely related to tree automata, we discuss deeply the relationship of our extension with weighted tree automata.
Partially supported by the ANR Project ECSPER (ANR-09-JCJC-0069).
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
Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proc. STOC 2004, pp. 202–211 (2004)
Borchardt, B., Fülöp, Z., Gazdag, Z., Maletti, A.: Bounds for tree automata with polynomial costs. Journal of Automata, Languages and Combinatorics 10(2/3), 107–157 (2005)
Caralp, M.: Automates à pile visible: ambiguité et valuation. Master’s thesis, Aix-Marseille Université (2011)
Caralp, M., Reynier, P.-A., Talbot, J.-M.: A polynomial procedure for trimming visibly pushdown automata. Technical Report hal-00606778, HAL, CNRS, France (2011)
Caralp, M., Reynier, P.-A., Talbot, J.-M.: VPA with Multiplicities: Finiteness and K-Boundedness. Technical Report hal-00697091, HAL, CNRS, France (2012)
Chan, T.-H., Ibarra, O.H.: On the finite-valuedness problem for sequential machines. Theoretical Computer Science 23, 95–101 (1983)
Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2008)
De Souza, R.: Étude structurelle des transducteurs de norme bornée. PhD thesis, ENST, France (2008)
Filiot, E., Raskin, J.-F., Reynier, P.-A., Servais, F., Talbot, J.-M.: Properties of Visibly Pushdown Transducers. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 355–367. Springer, Heidelberg (2010)
Fülöp, Z., Vogler, H.: Weighted Tree Automata and Tree Transducers. In: Handbook of Weighted Automata. Springer (2009)
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press (2009)
Sakarovitch, J., de Souza, R.: On the Decidability of Bounded Valuedness for Transducers. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 588–600. Springer, Heidelberg (2008)
Seidl, H.: On the finite degree of ambiguity of finite tree automata. Acta Inf. 26(6), 527–542 (1989)
Seidl, H.: Deciding equivalence of finite tree automata. SIAM J. Comput. 19(3), 424–437 (1990)
Seidl, H.: Finite tree automata with cost functions. Theor. Comput. Sci. 126(1), 113–142 (1994)
Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theor. Comput. Sci. 88(2), 325–349 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Caralp, M., Reynier, PA., Talbot, JM. (2012). Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness. In: Yen, HC., Ibarra, O.H. (eds) Developments in Language Theory. DLT 2012. Lecture Notes in Computer Science, vol 7410. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31653-1_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-31653-1_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31652-4
Online ISBN: 978-3-642-31653-1
eBook Packages: Computer ScienceComputer Science (R0)