Counting with rational functions
type: Item
instance of: scholarly article
title: Counting with rational functions
zbMATH Open document ID: 0664.68057
DOI: 10.1016/0304-3975(88)90020-5
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 4087030
zbMATH Keywords: automata
zbMATH Keywords: rational functions
zbMATH Keywords: free monoid
zbMATH Keywords: semaphore
zbMATH Keywords: counting function
zbMATH Keywords: factor distance
author: Christian Choffrut
author: Marcel Paul Schützenberger
reviewed by: Christophe Reutenauer
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90020-5
OpenAlex ID: W2005407474
cites work: Q3859267
cites work: Q4430300
cites work: Q3691074
cites work: Q3853135
cites work: Q4079524
cites work: A Characterization of Machine Mappings
cites work: Q5585020
cites work: Q3853827
cites work: Q5625457
cites work: The equation \(a_ M=b^ Nc^ P\) in a free group
cites work: Transductions des langages de Chomsky
cites work: On a Theorem of R. Jungen
cites work: Sur une variante des fonctions séquentielles
description: scientific article; zbMATH DE number 4087030