Abstract
We study deterministic pushdown automata operating with translucent input letters. These devices can be obtained by equipping classical deterministic pushdown automata with a translucency function which, depending on the current state, establishes the set of invisible input symbols: such symbols are skipped in the current move and dealt with in subsequent sweeps, while the first visible symbol from the current input head position is processed. Translucent deterministic pushdown automata can be returning, meaning that a new input sweep starts from the leftmost input symbol immediately after processing a visible symbol, or not. We show some incomparability results between the acceptance capability of returning and non-returning translucent deterministic pushdown automata and that of non-returning translucent deterministic and nondeterministic finite state automata. Then, we prove the non-closure of families of languages accepted by returning and non-returning translucent deterministic pushdown automata under concatenation, Kleene star, length-preserving and inverse homomorphism, reversal, and intersection with regular languages. In particular, arguments used to prove non-closure under this last language operation, enable us to answer a question on non-returning translucent deterministic finite state automata left open in the literature.
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
Similar content being viewed by others
References
Beier, S., Holzer, M.: Nondeterministic right one-way jumping finite automata. Inform. Comput. 284, 104687 (2022). https://doi.org/10.1016/J.IC.2021.104687
Bensch, S., Bordihn, H., Holzer, M., Kutrib, M.: On input-revolving deterministic and nondeterministic finite automata. Inform. Comput. 207, 1140–1155 (2009). https://doi.org/10.1016/j.ic.2009.03.002
Chigahara, H., Fazekas, S.Z., Yamamura, A.: One-way jumping finite automata. Int. J. Found. Comput. Sci. 27, 391–405 (2016). https://doi.org/10.1142/S0129054116400165
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)
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). https://doi.org/10.1007/3-540-60249-6_60
Kutrib, M., Malcher, A., Mereghetti, C., Palano, B., Raucci, P., Wendlandt, M.: Deterministic pushdown automata with translucent input letters. In: Day, J., Manea, F. (eds.) DLT 2024. LNCS, vol. 14791, pp. 203–217. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-66159-4_15
Meduna, A., Zemek, P.: Jumping finite automata. Int. J. Found. Comput. Sci. 23, 1555–1578 (2012). https://doi.org/10.1142/S0129054112500244
Mitrana, V., Pǎun, A., Pǎun, M., Couso, J.R.S.: Jump complexity of finite automata with translucent letters. Theoret. Comput. Sci. 992, 114450 (2024). https://doi.org/10.1016/j.tcs.2024.114450
Mráz, F., Otto, F.: Non-returning deterministic and nondeterministic finite automata with translucent letters. RAIRO Theor. Inform. Appl. 57, 8 (2023). https://doi.org/10.1051/ita/2023009
Nagy, B., Otto, F.: CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store. RAIRO Theor. Inform. Appl. 45, 413–448 (2011). https://doi.org/10.1051/ITA/2011123
Nagy, B., Otto, F.: Finite-state acceptors with translucent letters. In: Bel-Enguix, G., Dahl, V., De La Puente, A. (eds.) International Workshop on AI Methods for Interdisciplinary Research in Language and Biology (BILC 2011), pp. 3–13. SciTePress (2011). https://doi.org/10.5220/0003272500030013
Nagy, B., Otto, F.: On CD-systems of stateless deterministic R-automata with window size one. J. Comput. Syst. Sci. 78, 780–806 (2012). https://doi.org/10.1016/J.JCSS.2011.12.009
Nagy, B., Otto, F.: Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata. Acta Inform. 50, 229–255 (2013). https://doi.org/10.1007/S00236-012-0175-X
Otto, F.: Restarting automata and their relations to the Chomsky hierarchy. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 55–74. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45007-6_5
Otto, F.: A survey on automata with translucent letters. In: Nagy, B. (ed.) CIAA 2023. LNCS, vol. 14151, pp. 21–50. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-40247-0_2
Savitch, W.J., Vitányi, P.M.B.: Linear time simulation of multihead turing machines with head-to-head jumps. In: Salomaa, A., Steinby, M. (eds.) ICALP 1977. LNCS, vol. 52, pp. 453–464. Springer, Heidelberg (1977). https://doi.org/10.1007/3-540-08342-1_35
Acknowledgements
The authors wish to thank the anonymous referees for their valuable and helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kutrib, M., Malcher, A., Mereghetti, C., Palano, B., Raucci, P., Wendlandt, M. (2024). On Properties of Languages Accepted by Deterministic Pushdown Automata with Translucent Input Letters. In: Fazekas, S.Z. (eds) Implementation and Application of Automata. CIAA 2024. Lecture Notes in Computer Science, vol 15015. Springer, Cham. https://doi.org/10.1007/978-3-031-71112-1_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-71112-1_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-71111-4
Online ISBN: 978-3-031-71112-1
eBook Packages: Computer ScienceComputer Science (R0)