Abstract
Weighted restarting automata have been introduced to study quantitative aspects of computations of restarting automata. Here we study the special case of assigning words as weights from the semiring of formal languages over a given (output) alphabet, in this way generalizing the restarting transducers introduced by Hundeshagen (2013). We obtain several new classes of word relations in terms of restarting automata, which we relate to various types of pushdown relations.
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
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling. Prentice-Hall Inc., Upper Saddle River (1972)
Choffrut, C., Culik II, K.: Properties of Finite and Pushdown Transducers. SIAM J. Comput. 12(2), 300–315 (1983)
Hundeshagen, N.: Relations and Transductions Realized by Restarting Automata. Ph.D. thesis, Fachbereich Elektrotechnik/Informatik, Universität Kassel (2013)
Hundeshagen, N., Leupold, P.: Transducing by observing and restarting transducers. In: Freund, R., Holzer, M., Truthe, B., Ultes-Nitsche, U. (eds.) NCMA 2012. books@ocg.at, vol. 290, pp. 93–106. Österreichische Computer Gesellschaft, Vienna (2012)
Hundeshagen, N., Leupold, P.: Transducing by Observing Length-Reducing and Painter Rules. RAIRO - Theor. Inform. Appl. 48(1), 85–105 (2014)
Hundeshagen, N., Otto, F.: Characterizing the rational functions by restarting transducers. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 325–336. Springer, Heidelberg (2012)
Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 283–292. Springer, Heidelberg (1995)
Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On Monotonic Automata with a Restart Operation. J. Auto. Lang. Comb. 4(4), 287–312 (1999)
Kutrib, M., Messerschmidt, H., Otto, F.: On Stateless Two-Pushdown Automata and Restarting Automata. Int. J. Found. Comp. Sci. 21, 781–798 (2010)
Otto, F., Wang, Q.: Weighted Restarting Automata. The results of this paper have been announced at WATA 2014 in Leipzig, May 2014 (submitted)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Wang, Q., Hundeshagen, N., Otto, F. (2015). Weighted Restarting Automata and Pushdown Relations. In: Maletti, A. (eds) Algebraic Informatics. CAI 2015. Lecture Notes in Computer Science(), vol 9270. Springer, Cham. https://doi.org/10.1007/978-3-319-23021-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-23021-4_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23020-7
Online ISBN: 978-3-319-23021-4
eBook Packages: Computer ScienceComputer Science (R0)