An iterated uniform nite-state transducer executes the same length-preserving transduction in iterative sweeps. The rst sweep occurs on the input string, while any subsequent sweep processes the output of the previous one. We focus on unary inputs. We show that any unary regular language can be accepted by a deterministic iterated uniform nite-state transducer with at most maxf2%; pg + 1 states, % and p being the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. This state cost cannot be improved by using nondeterminism, and is de nitely lower than the state costs of equivalent classical models of nite-state automata.
The notion of an iterated uniform nite-state transducer (iufst) has been
introduced in [
A theoretical investigation of iufsts is motivated by the fact that iterated or
cascade transductions show up in numerous elds of computer science, e.g., in
natural language processing [
Deterministic and nondeterministic iufsts (the nondeterministic model
denoted by niufst) have been deeply studyied in [
In this paper, we construct size-e cient iterated transducers for general unary regular languages. We give our construction step by step, starting from nite unary languages. We show that nite unary languages with words of length up to ` can be accepted by an iufst with 2% states, % being the greatest prime in the factorization of `. Next, we switch to unary periodic languages, and prove that any n-periodic unary language can be accepted by an iufst with p states, p being the greatest prime in the factorization of n. By combining these two results, we get that any unary regular language is accepted by an iufst with at most maxf2%; pg + 1 states. We then show that these state costs cannot be improved by using nondeterminism, and that they are de nitely lower than the state costs of equivalent classical models of nite-state automata.
Due to the page limit, proofs and further results (some of which may be
found in [
De nitions and Preliminaries By the Fundamental Theorem of Arithmetic, any integer n > 1 univocally factorizes as n = Qis=1 pi i , for primes p1 < < ps and integers i > 0. For any n > 1, we let Zn = f0; 1; : : : ; n 1g be the ring of the remainders modulo n. Let be the set of words on a nite alphabet , including the empty word. The length of a word w is denoted by jwj. A language on is any set L .
A nondeterministic iterated uniform nite-state transducer (niufst) is a 8tuple T = hQ; ; ; q0; B; C; ; F i, with Q the set of internal states, the set of input symbols, the set of output symbols, q0 2 Q the initial state, B 2 n and C 2 n the left and right endmarkers, respectively, F Q the set of accepting states, and : Q ( [ ) ! 2Q the partial transition function. The niufst T halts if the transition function is unde ned or T enters an accepting state at the end of a sweep. The transduction is applied in multiple sweeps, and in any but the initial sweep it processes an output of the previous sweep. So, the transition function depends on symbols in [ . Let T (w) be the set of possible outputs yielded by T in a complete sweep on the input string w 2 ( [ ) . In a computation on input w 2 , the niufst T yields a sequence of words w1; : : : ; wi; wi+1; : : : 2 ( [ ) , with w1 2 T (BwC) and wi+1 2 T (wi) for i 1. An iterated uniform nite-state transducer is deterministic (iufst) whenever j (p; x)j 1, for all p 2 Q and x 2 ( [ ). In this case, we simply write (p; x) = (q; y) instead of (p; x) = f(q; y)g assuming that the transition function is a mapping : Q ( [ ) ! Q .
A computation is halting if there exists an r 1 such that T halts on wr, thus performing r sweeps. The input word w 2 is accepted by T if at least one computation on w halts at the end of a sweep in an accepting state. Otherwise it is rejected. Indeed, the output of the last sweep is not used. The language accepted by T is the set L(T ) de ned as L(T ) = f w 2 j w is accepted by T g.
For nondeterministic computations and some complexity bound, several
language acceptance modes are usually considered in the literature. Here, we deal
with the number of sweeps as complexity measure, and adopt the so-called
accept mode of acceptance [
A language L is unary whenever built on a single-letter alphabet. In
this case, we let L 0 . A unary language L 0 is n-periodic if there exists
R Zn such that L = f 0c n+R j c 0 and R 2 R g. We will always be
assuming that n is the minimal value de ning L. This is usually referred to as L
being properly n-periodic. To emphasize periodicity and R Zn, we express L
in the form Ln;R. By pumping arguments, we get that n states are necessary and
su cient for dfas and nfas to accept Ln;R. The minimal dfa for Ln;R consists
of a single cordless cycle of n states, with an initial state and nal states settled
according to R. On the other hand, for n factorizing as n = p1 1 p2 2 ps s ;
we have that any two-way dfa and nfa, or isolated cut-pint probabilistic nite
automaton (pfa) for Ln;R must have at least Ps
i=1 pi i states [
Any unary regular language is the disjoint union of a nite language and an
ultimately periodic language. So, it is de ned by three parameters `, n, R Zn:
The set L`, called the pre-periodic part of L`;n;R, is a nite unary language with
strings of length not exceeding `. The set f 0`+c n+R j c 0 and R 2 R g is the
periodic part of L`;n;R. As usual, we assume that the parameters ` and n are the
smallest possible de ning L`;n;R. Note that L`;n;R is accepted by a dfa whose
state digraph features an initial path of ` states joined to a cordless cycle of n
states. Clearly, the above recalled state lower bound for two-way dfas and nfas,
or isolated cut-point pfas for Ln;R carries over to L`;n;R as well. By simulation
results in [
Iterated Transduction and Unary Regular Languages We present our construction of state-e cient iufsts for unary regular languages by rst focusing on unary periodic languages, then considering nite unary languages, and nally getting to general unary regular languages. 3.1
For reader's ease of mind, we start by considering unary periodic languages of the form Ln = f 0c n j c 0 g, for n 1.
Theorem 1. Let n 2 factorize as n = Qis=1 pi i , with i > 0. The language Ln can be accepted by a ps-state r-iufst with r = Ps i=1 i sweeps.
The minimality { in terms of number of states { of the iufst for Ln designed in Theorem 1 is provided by a pumping argument in the following theorem, which also shows that nondeterminism cannot help in reducing state size: Theorem 2. Let n 2 factorize as n = Qis=1 pi i , with i > 0. Any iufst and niufst accepting Ln must use at least ps states, regardless of the number of performed sweeps.
Let us now move on to a slightly di erent version of Ln. Precisely, for any n 1 and a xed remainder R 2 Zn n f0g, we let Ln;R = f 0c n+R j c 0 g: The next theorem shows that this modi cation of Ln does not increase state and sweep complexity of acceptance on iterated transducers.
Theorem 3. Let n 2 factorize as n = Qis=1 pi i , with i > 0. The language Ln;R can be accepted by a ps-state r-iufst with r = Ps i=1 i sweeps.
Finally, we come to tackle the acceptance of a general unary n-periodic language Ln;R, for a xed set R Zn: Ln;R = f 0c n+R j c 0 and R 2 R g. Theorem 4. Let n 2 factorize as n = Qis=1 pi i , with i > 0. The language Ln;R can be accepted by a ps-state r-iufst with r = Ps i=1 i sweeps.
We notice that from Theorem 2 one may obtain that any iufst and niufst accepting Ln;R must use at least ps states, regardless the number of performed sweeps. In addition, as recalled in Section 2, we remark that n states are necessary and su cient for dfas and nfas to accept Ln;R, while Pis=1 pi i states are necessary for two-way dfas and nfas, and one-way isolated cut point pfas. 3.2
For any positive integer `, let L` be any unary language whose longest word has length `. In what follows, we assume ` 2. The case ` = 1 can be trivially managed by a 2-state dfa seen as a transducer.
Theorem 5. Let ` 2 factorize as ` = Qir=1 %i i , with i > 0. The language L` can be accepted by a (2%r)-state t-iufst with t = Pr i=1 i sweeps.
Any classical nite-state automata for L` needs at least ` states. By a pumping argument as in Theorem 2, iterated transduction needs at least %r states.
Finally, let us put things together. As addressed in Section 2, a general (in nite) unary regular language consists of the disjoint union of a (possibly empty) nite pre-periodic language and a ultimately periodic language. Hence, it can be de ned by three parameters `, n, and R Zn as where, with a slight abuse with respect to notation in Section 3.2, we intend L` as a nite unary language that is accepted by an `-state dfa. So, di erently from Section 3.2, from now on L` does not necessarily contain the unary word of length `. In the following theorem, we consider `; n 2. Otherwise, we have languages that can be trivially dealt with by our constructions in this paper. Theorem 6. Let `; n 2 factorize as n = Qis=1 pi i , ` = Qir=1 %i i , i; i > 0. The unary language L`;n;R can be accepted by an x-state t-iufst, where x = max f2%r; psg + , = 0 if %r < ps and 1 otherwise, and t = Pis=1 i + Pir=1 i.
By adapting the pumping argument in Theorem 2, we get that not less than maxf%r; psg states can be used to accept L`;n;R on iterated transducers. On the other hand, as recalled in Section 2, ` + n states are necessary and su cient for a dfa to accept L`;n;R, and not less than Ps i=1 pi i states on two-way dfas and nfas, and on isolated cut-point pfas are needed.
Acknowledgements. The authors wish to thank the anonymous referees.