Abstract
When designing and maintaining the information systems, there is a need to use parameterized automata, in which some components of the model that determine its behavior are replaced with variables. It has previously been shown that the complexity of many analysis and synthesis problems increases significantly when machines or programs have parameters. Nevertheless, it can be expected that for some classes of automata the complexity of certain important problems will remain low and the development of efficient algorithms will be possible. We present here the results of our study of some basic decision problems for finite state transducers parameterized on output data. When choosing this class of automata, we were guided by the intention of preserving the determinism of runs with uncertain values of some elements due to the presence of parameters in the model. We managed to show that for some decision problems their complexity remains low (NL-complete) even after parameters are added to the model, whereas the complexity of other problems that have efficient solutions for ordinary transducers increases significantly (from NL or P-completeness to NP-completeness and beyond) for their parameterized modifications.
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
Alur R., Henzinger T.A., Vardi M.Y.: Parametric real-time reasoning. In: Proceedings of the 25-th Annual ACM Symposium on Theory of Computing (STOC), pp. 592–601 (1993)
André, É., Lime, D., Roux, O.H.: Decision problems for parametric timed automata. In: Ogata, K., Lawford, M., Liu, S. (eds.) ICFEM 2016. LNCS, vol. 10009, pp. 400–416. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47846-3_25
Andre, E.: What’s decidable about parametric timed automata. Int. J. Softw. Tools Technol. Transf. 21, 203–219 (2019)
Balcazar, J.L., Gabarro, J., Santha, M.: Deciding bisimilarity is P-complete. Formal Aspects Comput. 4, 638–648 (1992)
Belkhir, W., Chevalier, Y., Rusinovitch, M.: Parametrized automata simulation and application to service composition. J. Symb. Comput. 69, 40–60 (2015)
Barcelo, P., Reutter, J., Libkin, L.: Parameterized regular expressions and their languages. Theoret. Comput. Sci. 474, 21–45 (2013)
Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inf. Comput. 97, 1–22 (1992)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Grumberg O., Kupferman O., Sheinvald S.: Variable automata over infinite alphabets. In: Proceedings of the 4-th International Conference on Language and Automata Theory and Applications (LATA), pp. 561–572 (2010)
Grumberg, O., Kupferman, O., Sheinvald, S.: An automata-theoretic approach for reasoning about parameterized systems and specifications. In: Proceedings of the 11-th International Symposium on Automated Technology for Verification and Analysis (ATVA), pp. 397–411 (2013)
Goller, S., Hillair, M.: Reachability in two-parametric timed automata with one parameter is EXPSPACE-complete. In: Proceedings of the 38-th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 36:1–36:18 (2023)
Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata - a survey. Inf. Comput. 209, 456–470 (2011)
Jones, N.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11, 68–85 (1975)
Kaminski, M., Francez, N.: Finite-memory automata. Theoret. Comput. Sci. 134, 329–363 (1994)
Kaminski, M., Zeitlin, D.: Finite-memory automata with non-deterministic reassignment. Int. J. Found. Comput. Sci. 21, 741–760 (2010)
Lenhardt, R.: Probabilistic automata with parameters. Master’s Thesis, University of Oxford, p. 63 (2009)
Shemesh, Y., Francez, N.: Finite state unification automata and relational languages. Inf. Comput. 114, 192–213 (1994)
Wiseman, H.M., Jones, S.J., Doherty, A.C.: Steering, entanglement, nonlocality, and the Einstein–Podolsky–Rosen paradox. Phys. Rev. Lett. 98 (2007)
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
Tang, T., Zakharov, V.A. (2024). On the Complexity of Decision Problems for Parameterized Finite State Synchronous Transducers. 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_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-71112-1_24
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)