Dizileri yeniden yazmak

Question

Bir alfabemiz olsun mesela $\Gamma = \{x,y\}$.

Diziden kastimiz bu alfabeden $n$ tane elemanin arka arkaya yazilmasi mesela $A_0=xxyxx$. Dizilerin boyundan ve alt dizilerinden bahdedebiliriz. Alt diziden kastimiz orjinal dizinin basindan veya  sonundan kesilmis dizileri dusunmeliyiz. mesela $xxxx$ $A_0$ dizisinin bilr alt dizisi degil ama $xyx$ $A_0$ in bir alt dizisi.

 

Bunlarin disinda elimizde bir kural sozlugumuz var mesela $R = \{ xy \to xx, xxx \to xxy\}$. Sozluk $K \to D$ seklinde elemanlardan olusuyor. $K$ ve $D$ birer dizi.$K$ ya anahtar $D$ ye deger diyelim.

Oyunumuz su :

Bize verilen bir $A_n$ dizisinden bir $A_{n+1}$ dizisi elde edecegiz.

$A_n$ in butun alt dizilerine bakacagiz. $A_n$ in bir alt dizisi kural sozlugunun anahtarlarindan birine esitse o alt dizi yerine anahtara denk gelen degeri yazacagiz. Oyle bir durum yok ise alt diziyi yazacagiz.

$A_{n+1}$ in biricik olmasi icin kural sozlugumuz uzerinde bir sinirlamaya gitmek gerekiyor tabii ki ama simdilik bunu es gecelim. (Aslinda bu da guzel bir soru $A_{n+1}$ in biricik olmasi icin kural sozlugu uzerine bir kisitlama getirin)
Kurallari sozlukte gorulme sirasina gore uygulayalim

Sorum su,

$A_0 = xy$ dizisinden ,

$R_1 = \{y \to yy\}$ kural sozlugu ile olusturulan $A_n$ dizisinin boyu exponensiyel olarak artiyor;

$R_2 = \{xy \to xxy \}$ kural sozlugu ile olusturulan $A_n$ dizisinin boyu linear olarak artiyor;

Oyle bir $R_3$ kural sozlugu verin ki dizinin boyu salinimli olsun.

Belki daha da genel olarak Her $\{a_n \in \mathbb{N} \}_{n \in \mathbb{N}}$ dizisi icin oyle bir kural sozlugu $R$ ve baslangic dizisi $B_0$ bulabilir misiniz ki oyunun her adimindaki dizinin $B_n$ boyu $a_n$ e esit olsun.

Comments

$A_0$ ve $R_1$ ile başladığımda $xy, xy^2, xy^4, \ldots$ diye devam ediyor dimi?

$A_0$ ve $R_2$ ile başladığımda $xy, x^2y, x^3y, \ldots$ diye devam ediyor?

Ilkinin ve ikincisinin artışının eksponensiyel ve lineer arttığını gördüm. Salınımlı derken ne demek istiyorsun, onu anlamadım? Son soruyu da anlamadım :( Bana bir doğal sayı dizisi vereceksin, ben de öyle bir ilk kelime ve kural sözlüğü bulacağım ki kelimelerin boyları o sayı dizisine göre değişecek. Anlamışım galiba?

---

Kural sözlüğü sonlu olacak herhalde dimi?

---

$A_0 = (xy)^3 = xyxyxy$ olsun ve $R = \{ yxy \to x \}$ olsun. $A_1=xxxy$ mi olacak $A_1=xyxx$ mi olacak? Yani biriciklik için başka şartlar da eklemek gerekiyor galiba, mesela alt dizileri de soldan sağa okuyup ilk gördüğümüzü değiştirmek gibi?

---

Soldan saga okuyoruz gibi dusunmustum ben. uslu ifade ile gostermek guzel fikirmis.Kural sozlugu sonlu olacak evet. Salinimli derken dizinin boyu bir artsin bir azalsin istiyorum. evet evet bayaa dogru anlamissin her seyi

---

Fancy bir şeyler diyeyim: (Bunlar soruyla tamamen alakasız, kafa açmak için)

1) Bu xy dizilerini bir ağaç gibi düşünebiliriz (çizge kuramı). Boş kelime en altta, ondan çıkan iki dal x ve y'ye gidiyor birinci kata. Sonra onlardan çıkan dallar ikinci katta x^2, xy (x'den çıkanlar) ve yx, y^2'ye gidiyor (y'den çıkanlar). $R$ sözlüğü senin bu ağaç üzerindeki yerini değiştiriyor. Bu ağaç üzerinde zıplaya zıplaya gidiyorsun. Sana bir $a_n$ dizisi veriyorum. Ağaç üzerinde öyle bir başlangıç noktası ve bir $R$ sözlüğü bulabilir misin ki $n$'inci adımında kendini $a_n$'inci adımda bul?

2) Sonsuzluk işaretini düşün, yan yatmış sekiz. Sen tam ortasında sekizin birleşme noktasında duruyorsun. Sol tarafında ve sağ tarafında birer çember var yani. Sol çemberde saat yönünde tam bir tur atınca $x$ hareketi yapmış ol, sağ çemberde saat yönünde tam bir tur atınca $y$ hareketi yapmış ol. xy-kelimelerini böyle de düşünebilirsin. Yararlı mı bilmiyorum.

3) Bir de bunu free group modulo relations gibi de düşünebiliriz biraz değiştirerek ama o zaman soru ne şekle girer bilemiyorum.

---

3 icin kurallar biricik ise monoid gibi de gorebiliriz sanirim

2 icin peki alfabem $\Gamma = \{x,y,z\}$ ise ne yapacagim uc tane loop u olan bir sey mi canlandirmaliyim kafamda. Bir nevi unvinding number gibi oldu

1 i tam anlamadim ya. benim sordugum son soruya benziyor sanki hatta ayni galiba dogru mu anladim.

elementer islemlerini bu sistemde gostermek zor olmasa gerek gibi dusunuyorum toplama cikarma bolme sanki sonlu kurallar sozlugu ile ifade edilebilir gibi bir his icindeyim.

Benim cikis noktam hucresel otomatlardi aslinda. En basit hucresel otomatlar (256 tane var zaten) su sekilde:

elimizde bir $a_n^t$ var ve bu dizi sifir ve birlerden olusuyor

$a_n^{t+1} = f(a_{n-1}^t,a_{n}^t,a_{n+1}^t,)$

yani bir sonraki adimi hesaplarken su an bulundugum noktaya sagina ve soluna bakiyorum. 3 arguman kabul eden boolean fonksiyonu bu noktalarda degerlendiriyorum.

Bu basit kurallar zinciri cok ilginc sonuclar cikarabiliyor.

 

 Sanirim buna (benim sorduguma) benzer bir sisteme "string rewriting" veya "abstract rewriting system" deniyor.

 

---

Kural kumesini sonlu tutmazsak aritmetik uretmek mumkun sanki

$R_\omega = \{ \mathbb{N}_i \mathbb{N}_j + \to \mathbb{N}_{i+j, } \mathbb{N}_i \mathbb{N}_j \times \to \mathbb{N}_{ij, \cdots } \}$

---

Bazi yeniden yazma kurallari sagdan sola ve soldan saga farketmezken bazilarinda farkediyor. Bu onemli bir ayrim olabilir.  Baska onemli bir ayrim ise bazi yeniden yazma kurallari bir sure sonra sabitleniyor ve hic bir degisim olmuyor olabilir.