Linear-Size Log-Depth Negation-Limited Inverter for /c-tonic 0/1 Sequences

摘要

A binary sequence x_1,..., x_n is called fc-tonic if for 1 ≤ i ≤ n-1 the number of i's such that Xi ≠ x_(i+1) is at most k. In this paper, we give the construction of a circuit inverting /c-tonic sequences, which has size O((log k)·n) depth O(logk) o loglogn + logn) and contains log2 n + O(loglogn) NOT gates. Our construction improves all parameters of the construction by Sato, Amano and Maruoka, whose size is O(kn) and depth is O(fclog n) using O(fclogn) NOT gates. If k = 0(1), the previous construction needs O(log2n) depth, but our inverter has linear size and log depth using O(logn) NOT gates. Beals, Nishino and Tanaka have shown the construction of a size O(nlogn) depth O(logn) inverter for all sequences with riog2(n + l)l NOT gates. If k = n~(o(1)) our construction reduces the size to o(n log n) with the same depth and only O(logiogn) increase of the number of NOT gates. Our idea on the construction of an inverter for k-tonic sequences also give an improvement for a circuit sorting fc-tonic sequences from the construction by Sato, Amano and Maruoka.