Limited semaphore codes (Q1204129): Difference between revisions

An alphabet \(A\) is a set of symbols called letters. A word over \(A\) is a finite catenation of letters. \(A^*\) denotes a free monoid over \(A\) which includes an empty word represented by 1. A subset \(X\) of \(A^ +=A\backslash 1\) is called a code over \(A\) if \(x_ 1x_ 2\cdots x_ n=y_ 1 y_ 2\cdots y_ m\) with \(x_ i,y_ i\in X\), then \(n=m\) and \(x_ i=y_ i\) for every \(i\), \(1\leq i\leq n\). A word in \(X\) is called an \(X\)-word. A code \(X\) is called a uniformly synchronous code if for some non-negative integer \(d\), \(uxv\in X^*\) with \(x\in X^ d\), \(u,v\in A^*\) implies \(ux\), \(xv\in X^*\), where \(X^*\) is a free monoid over \(X\). The smallest \(d\) satisfying this property is called the synchronizing delay of \(X\) denoted by \(\sigma(x)\). A code \(X\) is right complete if, for any \(u\in A^*\) there exists a \(t\) such that \(ut\in X^*\). A code \(X\) satisfies the \(F-d\) condition if \(A^ + X^ d A^ +\cap X=\emptyset\), where \(d\) is a natural number. A code \(X\) is called a semaphore code iff \(A^* XA^ +\cap X=\emptyset\) and \(X\) is right complete, equivalently iff \(X\) is a right complete prefix code satisfying the \(F-1\) condition. A code \(X\) is a synchronous code if there exists an \(x\in A^*\) such that \(A^* x\subseteq X^*\) and \(x\) is called a synchronizing word for \(X\). A code \(X\) is called \(d\)-synchronous iff \(A^* X^ d\subseteq X^*\). Let \(m\), \(n\) be any two non-negative integers such that \(m+n\neq 0\). A code \(X\) over \(A\) is said to be an \((m,n)\)-limited code if for any sequence \(\{u_ 0,u_ 1,\dots,u_{m+n}\}\) in \(A^*,u_ 0 u_ 1,u_ 1 u_ 2,\dots,u_{m+n-1} u_{m+n}\in X^*\) implies \(u_ m\in X^*\). A limited code is an \((m,n)\)-limited code for some non-negative integers \(m\), \(n\) with \(m+n\neq 0\). Some conditions are given for when a semaphore code, not necessarily limited, is a synchronous code and vice-versa. It is observed that limited semaphore codes are not only synchronous but also \(d\)-synchronous. It is shown that 1-synchronous codes are always semaphore codes as well as limited codes and the structure of certain 1- synchronous codes are shown to be exactly (1,0)-limited semaphore codes. It is assumed that no code is a subset of \(A\).