A Consideration on Locally Computable Coding and Its Code Length

• Nagaura Wataru

  Department of Information Systems Interdisciplinary Graduate School of Engineering Sciences Kyushu University

• Yasuura Hiroto

  Department of Information Systems Interdisciplinary Graduate School of Engineering Sciences Kyushu University

Bibliographic Information

Other Title

• 単項演算に対する局所計算可能な符号化とその符号長に関する考察

Abstract

When an operation defined on a finite set can be realized under a coding C by a computation rule in which each digit of the result of the operation depends on at most k digits of the operand, the operation is said to be k-locally computable under the coding C. In this report, we show a lower bound of the code length which is needed when all logical functions with n inputs and n outputs are locally computable under a coding. The result is that the code length increases as an exponential function of n.

Journal

• IPSJ SIG Notes

  IPSJ SIG Notes 93 (48), 103-110, 1993-05-28

  Information Processing Society of Japan (IPSJ)

Details

• CRID: 1570572702210950016
• NII Article ID: 110002812081
• NII Book ID: AN1009593X
• ISSN: 09196072
• Text Lang: ja
• Data Source:
  • CiNii Articles