Counting with rational functions (Q1115616): Difference between revisions

The authors characterize a special class of rational functions from a free monoid \(A^*\) into a cyclic free monoid \(t^*\). A semaphore is a subset H of \(A^*\) such that no word in H is a (connected) factor of another word in H. A partial function \(\alpha\) : \(A^*\to t^*\) is called a counting function if there exist \(n\geq 1\), rational semaphores \(H_ 1\),..., \(H_ n\), rational numbers \(r_ 1\),..., \(r_ n\), a partition \(dom(\alpha)=X_ 1 \cup...\cup X_ m\) and rational numbers \(s_ 1\),..., \(s_ m\) such that for \(j=1\),..., m and any word w in \(X_ j\), one has \(| w\alpha | =s_ j+\sum_{1\leq i\leq n}r_ i | w|_{H_ i}.\) Here, \(| w|_ H\) stands for the number of occurrences of elements of H as factors of w. The factor distance d(u,v) between two words is \(| u| +| v| -2| x|\), where x is a factor common to u and v and of maximal length. The main result is that a partial function \(\alpha\) : \(A^*\to t^*\) is a counting function if and only if \(\alpha\) is rational and \(\alpha\) satisfies the Lipschitz condition: \(\forall u, v\in\) dom(\(\alpha)\), \(d(\alpha (u),\quad \alpha (v))\leq k d(u,\quad v),\) where k depends on \(\alpha\) only.