Portal de Periódicos da CAPES

Bounds on the size and transmission rate of communications protocols

1982; Elsevier BV; Volume: 8; Issue: 3 Linguagem: Inglês

10.1016/0898-1221(82)90043-8

1873-7668

Alfred V. Aho, A.D. Wyner, Mihalis Yannakakis, Jeff Ullman,

Cellular Automata and Applications

Using a pair of finite-state automata to model the transmitter-receiver protocol in a data communications system, we derive lower bounds on the size of automata needed to achieve reliable communication across an error-prone channel. We also show that, at the cost of increasing the size of the automata, a transmission rate close to the theoretical maximum can be achieved.