Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers

• Autorzy: Kutrib Martin , Malchers Andrea , Mereghetti Carlo , Palano Beatrice

Identyfikatory

DOI

10.3233/FI-222113

• Języki publikacji: EN

Abstrakty

EN

An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTs are "one-way" devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace (lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic.

Słowa kluczowe

EN

descriptional complexity; Iterated transducers; language hierarchies; nondeterminism; sweep complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 4
• Strony: 337--356
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Kutrib Martin

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany.

autor

Malchers Andrea

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany.

autor

Mereghetti Carlo

• Dip. di Informatica "G. degli Antoni", Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy.

autor

Palano Beatrice

• Dip. di Informatica "G. degli Antoni", Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy.

Bibliografia

• [1] Kutrib M, Malcher A, Mereghetti C, Palano B. Deterministic and Nondeterministic Iterated Uniform Finite-State Transducers: Computational and Descriptional Power. In: Computability in Europe (CiE 2020), volume 12098 of LNCS. Springer, 2020 pp. 87-99. doi.:10.1007/978-3-030-51466-2 8.
• [2] Kutrib M, Malcher A, Mereghetti C, Palano B. Descriptional Complexity of Iterated Uniform Finite-State Transducers. In: Hospodár M, Jirásková G, Konstantinidis S (eds.), Descriptional Complexity of Formal Systems (DCFS 2019), volume 11612 of LNCS. Springer, 2019 pp. 223-234. doi:10.1007/978-3-030- 23247-4 17.
• [3] Kutrib M, Malcher A, Mereghetti C, Palano B. Descriptional Complexity of Iterated Uniform Finite-State Transducers. Inf. Comput., 2022. 284:104691. doi:10.1016/j.ic.2021.104691.
• [4] Friburger N, Maurel D. Finite-State Transducer Cascades to Extract Named Entities in Texts. Theor. Comput. Sci., 2004. 313(1):93-104. doi:10.1016/j.tcs.2003.10.007.
• [5] Ginzburg A. Algebraic Theory of Automata. Academic Press, 1968.
• [6] Hartmanis J, Stearns RE. Algebraic Structure Theory of Sequential Machines. Prentice-Hall, 1966.
• [7] Citrini C, Crespi-Reghizzi S, Mandrioli D. On Deterministic Multi-Pass Analysis. SIAM J. Comput., 1986. 15(3):668-693. doi:10.1137/0215049.
• [8] Bordihn H, Fernau H, Holzer M, Manca V, Martín-Vide C. Iterated Sequential Transducers as Language Generating Devices. Theor. Comput. Sci., 2006. 369(1-3):67-81. doi:10.1016/j.tcs.2006.07.059.
• [9] Manca V. On the Generative Power of Iterated Transductions. In: Words, Semigroups, and Transductions – Festschrift in Honor of Gabriel Thierrin. World Scientific, 2001 pp. 315-327. doi:10.1142/9789812810908 0024.
• [10] Pierce A. Decision Problems on Iterated Length-Preserving Transducers. Bachelor’s thesis, SCS Carnegie Mellon University, Pittsburgh, 2011.
• [11] Bednárová Z, Geffert V, Mereghetti C, Palano B. The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata. Theoret. Comput. Sci., 2012. 449:23-36. doi:10.1016/j.tcs.2012.05.009.
• [12] Bertoni A, Mereghetti C, Palano B. Trace Monoids with Idempotent Generators and Measure-Only Quantum Automata. Natural Computing, 2010. 9(2):383-395. doi:10.1007/s11047-009-9154-8.
• [13] Bianchi MP, Mereghetti C, Palano B. Quantum Finite Automata: Advances on Bertoni’s Ideas. Theoret. Comput. Sci., 2017. 664:39-53. doi:10.1016/j.tcs.2016.01.045.
• [14] Bednárová Z, Geffert V, Mereghetti C, Palano B. Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height. In: Bulatov A, Shur A (eds.), Computer Science in Russia (CSR 2013), volume 7913 of LNCS. Springer, 2013 pp. 100-111. doi:10.1007/978-3-642-38536-0 9.
• [15] Bednárová Z, Geffert V, Mereghetti C, Palano B. Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height. J. Comput. Syst. Sci., 2017. 90:99-114. doi:10.1016/j.jcss.2017.06.007.
• [16] Jakobi S, Meckel K, Mereghetti C, Palano B. Queue Automata of Constant Length. In: Jürgensen H, Reis R (eds.), Descriptional Complexity of Formal Systems (DCFS 2013), volume 8031 of LNCS. Springer, 2013 pp. 124-135. doi:10.1007/978-3-642-39310-5 13.
• [17] Holzer M, Kutrib M. Descriptional Complexity - An Introductory Survey. In: Martín-Vide C (ed.), Scientific Applications of Language Methods, pp. 1-58. Imperial College Press, 2010. doi:10.1142/9781848165458 0001.
• [18] Mealy GH. A Method for Synthesizing Sequential Circuits. Bell System Tech. J., 1955. 34:1045-1079. doi:10.1002/j.1538-7305.1955.tb03788.x.
• [19] Mereghetti C. Testing the Descriptional Power of Small Turing Machines on Nonregular Language Acceptance. Int. J. Found. Comput. Sci., 2008. 19:827-843. doi:10.1142/S012905410800598X.
• [20] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
• [21] Malcher A, Mereghetti C, Palano B. Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals. Theoret. Comput. Sci., 2012. 449:119-133. doi:10.1016/j.tcs.2012.04.007.
• [22] Jones ND. Space-Bounded Reducibility among Combinatorial Problems. J. Comput. System Sci., 1975. 11:68-85. doi:10.1016/S0022-0000(75)80050-X.
• [23] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979. ISBN:0-7167-1044-7.
• [24] Holzer M, Kutrib M. Descriptional and Computational Complexity of Finite Automata - A Survey. Inf. Comput., 2011. 209(3):456-470. doi:10.1016/j.ic.2010.11.013.
• [25] Li M, Vitányi PMB. An Introduction to Kolmogorov Complexity and Its Applications. Springer, 3rd edition, 2008.
• [26] Hartmanis J. Computational Complexity of One-Tape Turing Machine Computations. J. ACM, 1968. 15(2):325-339. doi:10.1145/321450.321464.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)