Uniformly synchronous codes

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)

Review text

Various relationships between synchronization and limitedness properties are investigated for prefix and biprefix codes. The prefix codes \(X\) over an alphabet \(A\) which are uniformly synchronous are characterized as the limited codes such that the \(F\)-\(d\) condition holds (i.e., codes with \(A^ +X^ dA^ +\cap X=\emptyset\)) for some natural number \(d\). A biprefix code of synchronization delay \(n\) is \((p,q)\)-limited with \(p+q=2n+1\). A biprefix code with the \(F\)-\(1\) condition has synchronization delay \(n\) if and only if it is \((2n+1,0)\)-limited but not \((2n-1,0)\)-limited. A code is a maximal prefix code with synchronization delay \(n\) if and only if the code is \(n\)-synchronous but not \((n-1)\)- synchronous. While 1-synchronous codes are known to be semaphore codes, an example is given to show that 2-synchronous codes are not necessarily semaphore codes. The 2-synchronous semaphore codes are characterized and necessary and sufficient conditions are also given for a semaphore code to be \(n\)-synchronous for an arbitrary \(n\).

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Uniformly synchronous codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1209281)