×

Iterated uniform finite-state transducers: descriptional complexity of nondeterminism and two-way motion. (English) Zbl 07770052

Summary: An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep takes place on the input string, while any subsequent sweep works on the output of the previous one. We consider devices with one-way motion and two-way motion, that is, sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we first study devices that perform a constant number of sweeps, which are known to characterize exactly the regular languages. We determine the descriptional costs of removing two-way motion, nondeterminism, and sweeps, and, in particular, the costs for the conversion to deterministic or nondeterministic finite automata. Moreover, the special case of unary languages is investigated, and a language family is presented that is immune to two-way motion and almost immune to nondeterminism, in the sense that these resources do not help in reducing the number of states and/or sweeps. Finally, we look at devices that perform a non-constant number of sweeps. Here, it turns out that in the deterministic case two-way motion is more powerful than one-way motion, whereas nondeterminism and one-way motion can be more powerful than determinism and two-way motion.

MSC:

68Q45 Formal languages and automata

References:

[1] Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano, Boolean language opera-tions on nondeterministic automata with a pushdown of constant height. In: A. A. Bu-latov, A. M. Shur (eds.), Computer Science -Theory and Applications, 8th Interna-tional Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013, Proceedings. LNCS 7913, Springer, 2013, 100-111. · Zbl 1362.68139
[2] Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano, Removing nondetermin-ism in constant height pushdown automata. Information and Computation 237 (2014), 257-267. · Zbl 1360.68539
[3] A. Bertoni, C. Mereghetti, B. Palano, Trace monoids with idempotent generators and measure-only quantum automata. Natural Computing 9 (2010) 2, 383-395. · Zbl 1207.68181
[4] M. P. Bianchi, C. Mereghetti, B. Palano, Quantum finite automata: Advances on Bertoni’s ideas. Theoretical Computer Science 664 (2017), 39-53. · Zbl 1359.68159
[5] H. Bordihn, H. Fernau, M. Holzer, V. Manca, C. Martín-Vide, Iterated se-quential transducers as language generating devices. Theoretical Computer Science 369 (2006) 1-3, 67-81. · Zbl 1142.68420
[6] C. Citrini, S. Crespi-Reghizzi, D. Mandrioli, On deterministic multi-pass analysis. SIAM Journal on Computing 15 (1986) 3, 668-693. · Zbl 0611.68051
[7] N. Friburger, D. Maurel, Finite-state transducer cascades to extract named entities in texts. Theoretical Computer Science 313 (2004) 1, 93-104. · Zbl 1069.68107
[8] A. Ginzburg, Algebraic Theory of Automata. Academic Press, 1968. · Zbl 0195.02501
[9] G. Hardy, E. Wright, An Introduction to the Theory of Numbers. 5 edition, Oxford University Press, 1979. · Zbl 0423.10001
[10] J. Hartmanis, R. E. Stearns, Algebraic Structure Theory of Sequential Machines. Prentice-Hall, 1966. · Zbl 0154.41701
[11] F. C. Hennie, One-tape, off-line Turing machine computations. Information and Con-trol 8 (1965), 553-578. · Zbl 0231.02048
[12] S. Jakobi, K. Meckel, C. Mereghetti, B. Palano, Queue automata of constant length. In: H. Jürgensen, R. Reis (eds.), Descriptional Complexity of Formal Sys-tems, 15th International Workshop, DCFS 2013, London, Canada, July 22-25, 2013, Proceedings. LNCS 8031, Springer, 2013, 124-135. · Zbl 1388.68173
[13] S. Jakobi, K. Meckel, C. Mereghetti, B. Palano, The descriptional power of queue automata of constant length. Acta Informatica 58 (2021) 4, 335-356. · Zbl 1520.68058
[14] M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, Descriptional complexity of iterated uniform finite-state transducers. In: M. Hospodár, G. Jirásková, S. Kon-stantinidis (eds.), Descriptional Complexity of Formal Systems, 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17-19, 2019, Proceedings. LNCS 11612, Springer, 2019, 223-234. · Zbl 1434.68272
[15] M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, Deterministic and nonde-terministic iterated uniform finite-state transducers: Computational and descriptional power. In: M. Anselmo, G. D. Vedova, F. Manea, A. Pauly (eds.), Beyond the Horizon of Computability, 16th Conference on Computability in Europe, CiE 2020, Fis-ciano, Italy, June 29-July 3, 2020, Proceedings. LNCS 12098, Springer, 2020, 87-99. · Zbl 1540.68121
[16] M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, Iterated uniform finite-state transducers on unary languages. In: T. Bureš, R. Dondi, J. Gamper, G. Guerrini, T. Jurdziński, C. Pahl, F. Sikora, P. W. H. Wong (eds.), SOFSEM 2021: Theory and Practice of Computer Science, 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25-29, 2021, Proceedings. LNCS 12607, Springer, 2021, 218-232. · Zbl 1490.68128
[17] M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, Computational and descrip-tional power of nondeterministic iterated uniform finite-state transducers. Fundamenta Informaticae 185 (2022) 4, 337-356. · Zbl 1540.68120
[18] V. Manca, On the generative power of iterated transductions. In: M. Ito, Gh. Păun, S. Yu (eds.), Words, Semigroups, and Transductions -Festschrift in Honor of Gabriel Thierrin. World Scientific, 2001, 315-327. · Zbl 1499.68188
[19] G. H. Mealy, A method for synthesizing sequential circuits. The Bell System Technical Journal 34 (1955), 1045-1079.
[20] C. Mereghetti, Testing the descriptional power of small Turing machines on nonreg-ular language acceptance. International Journal of Foundation of Computer Science 19 (2008), 827-843. · Zbl 1156.68021
[21] C. Mereghetti, B. Palano, G. Pighizzini, Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata. RAIRO -Theoretical Informatics and Applications 35 (2001) 5, 477-490. · Zbl 1010.68068
[22] C. Mereghetti, G. Pighizzini, Two-way automata simulations and unary languages. Journal of Automata, Languages and Combinatorics 5 (2000), 287-300. · Zbl 0965.68043
[23] M. O. Rabin, Probabilistic automata. Information and Control 6 (1963), 230-245. (Received: March 31, 2021; revised: October 7, 2021) · Zbl 0182.33602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.