Kode Gray dan Algoritma Pembangkit untuk Fungsi Tumbuh Terestriksi Berbatas

Abstract

Dalam penelitian terdahulu penulis beserta rekan mendefinisikan relasi urut yang menginduksi 3-kode Gray untuk kelas fungsi tumbuh terrestriksi berbatas. Sebagai penelitian lanjutan, paper ini memberikan rancangan 1-kode Gray untuk kelas tersebut beserta algoritma pembangkit dengan kompleksitas constant amortized time (CAT). Berbeda dengan penelitian terdahulu yang menggunakan relasi urut, pendekatan yang dilakukan pada penelitian ini adalah dengan memanfaatkan sifat defining sequence dari kelas fungsi tumbuh terrestriksi berbatas yang memiliki sedikitnya dua anggota tetap, yaitu 0 dan 1. Rancangan kode Gray dalam penelitian ini dibangun berdasarkan rancangan kode Gray Mansour-Vajnovszki, yang dimodifikasi untuk memperoleh urutan defining sequence yang lebih natural dan lebih mjudah diimplementasikan pada bahasa pemrograman.