Kısaltıcı mekanizmasının bir boyutlu hücresel hareketlilerde gerçek zamanda simulasyonu.

Özet

Girdi şeridi üzerinde, kısaltım işlemleri yaparak girdiyi tanıyan ve "kısaltıcı" olarak adlandırılan mekanizmalar vardır. Bu çalışmada, zincir adı verilen bir-boyutlu hücresel hareketlilerin belirlenimli kısaltıcıları gerçek zamanda simule edebildiği ortaya konmuştur. Zincirler, sonlu durumlu Moore makinelerinden oluşan bir-boyutlu hücresel yapılardır. Zincirde her hücrenin girişi, her iki yanındaki komşularının çıkışlarına bağlıdır. Burada, verilen herhangi bir belirlenimli kısaltıcıya karşılık, onu simule eden bir zincir olduğu gösterilirken, yapımsal ispat yöntemi kullanılmıştır. Kısaltıcı mekanizmasından hareketle kurulan zincir, dengeli parantezleri ve ortası belli palindromları kabul etmektedir. Zincir, bu dizgileri kabul ederken kısaltıcıya göre daha az sayıda geçiş yapmaktadır.

Abstract

There are some mechanisms called shrinkers which recognize the input by performing shrinking operations on the input tape. In this work, it is shown that one-dimensional cellular automata called chains can simulate deterministic shrinkers in real-time. Chains are one-dimensional cellular structures consisting of finite-state Moore machines. In a chain the input of each cell is connected to the outputs of the two neighboring cells on each side. Here a constructive proof method is employed in showing that a chain exists corresponding to any given deterministic shrinker which simulates it. The chain which is constructed corresponding to a shrinker can accept balanced parenthesis and palindromes with distinguished centers. In accepting these strings a chain performs less number of transitions with respect to shrinkers.