%0 Conference Proceedings
%T Descriptional Complexity of Iterated Uniform Finite-State Transducers
%+ Institut für Informatik [Gießen]
%+ Università degli Studi di Milano = University of Milan (UNIMI)
%A Kutrib, Martin
%A Malcher, Andreas
%A Mereghetti, Carlo
%A Palano, Beatrice
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 223-234
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_17
%K Iterated transducers
%K State complexity
%K Sweep complexity
%K Decidability
%Z Computer Science [cs]Conference papers
%X We introduce the deterministic computational model of an iterated uniform finite-state transducer (iufst). A iufst performs the same length-preserving transduction on several left-to-right sweeps. The first sweep takes place on the input string, while any other sweep processes the output of the previous one. The iufst accepts or rejects upon halting in an accepting or rejecting state along its sweeps. First, we focus on constant sweep bounded iufsts. We study their descriptional power vs. deterministic finite automata, and the state cost of implementing language operations. Then, we focus on non-constant sweep bounded iufsts, showing a nonregular language hierarchy depending on sweep complexity. The hardness of some classical decision problems on constant sweep bounded iufsts is also investigated.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387284/document
%2 https://inria.hal.science/hal-02387284/file/480958_1_En_17_Chapter.pdf
%L hal-02387284
%U https://inria.hal.science/hal-02387284
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612