Search

Bu çalışmada, Türkiye'deki nehir akımları mevsimlik verilerinin parametrik ve non-parametrik yöntemlerle trend analizleri araştırılmıştır. EİEİ tarafından toplanan Türkiye'deki nehir akımları verilerinin mevsimlik değerleri kullanılmıştır. Trend analizinin tespiti için parametrik yöntemlerden Zaman Serileri- En Küçük Kareler yöntemi ile non-parametrik yöntemlerden üç farklı trend testi seçilmiştir. Bunlar Spearman'ın Rho testi, Mann Kendall testi ve Seasonal Kendall testidir. Trendlerin lineer eğimleri (birim zamandaki değişim), Sen tarafından geliştirilen parametrik olmayan bir metot kullanılarak hesaplanmıştır., In thıs study, the trend analysis of the rate of river flows in Turkey deperding an seasonal data with parametric and non-parametric approaches is being investigated. The seasonal values of the rate of river flows in Turkey abtained by EIEI are used. In order to identify the trend analysis, time series among the parametric approaches-the smallest sguare approach and three differest trend tests among the non-parametric approaches are selacted. These tests are the Spearman?s Rho test, the Mann-Kendall test and the Seasonal Kendall test. The linear slopes (change per unit time) of trends are calculated by using a non-parametric estimator developed by Sen.

ÖZET Kıbrıs Adası stratejik konumu sebebiyle tarih boyunca dünyada egemen olan güçlerin hedefinde yer almış ve üzerinde sürekli güç mücadeleleri yaşanmıştır. Yaklaşık üç yüz yıl Osmanlı egemenliğinde kaldıktan sonra İngiltere'nin hakimiyeti altına giren Kıbrıs Adası, üzerinde yaşanan güç mücadelesi sonucunda toplumsal kargaşaya sürüklenmiştir. 1954'ten sonra İngilizlerin kontrolünden çıkmaya başlayan Ada' da yaşanan olaylar sonucunda Türkiye de Kıbrıs ile ilgilenmeye, burada yaşayan soydaşlarına sahip çıkmaya başlamıştır. Yaşanan olaylara çözüm bulmak, Türk ve Rum toplumlarının bir çatı altında yaşamasını sağlamak maksadıyla 1959 yılında Kıbrıs Cumhuriyeti kurulmuş, ancak Türk toplumu Rumlar tarafından azınlık olarak görüldüğünden yasayla verilmiş olan haklan ellerinden alınmıştır. 1964'te Kıbrıs Cumhuriyetinin sona ermesi ve devamında yaşanan olayların Türklerin katledilmesine dönüşmesi üzerine Türkiye 1974 yılında müdahale etmiş ve o güne kadar Kıbrıs'ta dağınık olarak baskı altında yaşayan Türklerin güvenliğini sağlamış ve Ada'nın kuzeyinde bir Türk bölgesi oluşturmuştur. 1 974 müdahalesi Türkiye tarihinde bir dönüm noktasıdır. Türkler Misak-ı Milli sınırları dışında tekrar toprak kazanmışlardır. 1983 tarihi ise, Ada'daki Türkleri sürekli azınlık olarak gören Rumlara karşı atılmış tarihi bir adımdır. Rum Liderliği o güne kadar eşit statüde görmediği Türk'lerin Devlet Başkam ile müzakere noktasına gelmiştir. Üstelik kendilerinin ve Türkiye hariç hiçbir devletin tanımadığı bir devletle. Kuzey Kıbrıs Türk Cumhuriyeti'nin bağımsızlık ilam, tanınsa da tanınmasa da bir gerçektir ve gücünü Türk Devleti ve Türk halkından almaktadır. ABSTRACT Cyprus Island had been taking part the objectives of the dominant powers and the struggles had been going on over it during the history for its strategically important location. Cyprus which had been dominated by the Great Britain after 300 years domination of the Ottoman Empire was dragged to the civil war the result of the power struggles. The result of the incidents seen on the Island which was out of the control of the Great Britain after 1954, Turkey regarded the Cyprus and claimed the rights of the Turkish minority. Cyprus republic was declared in 1959 in order to find solution of the turmoil and to enable living together under the same roof of both cypriots, but Turkish Cypriot assumed the minority deprived of their rights given by the law. Turkey interfered the Island in 1974 after coming end of the Cyprus Republic and afterwards incidents which were formed as a genocide and to provide security of the Turkish cypriot who were living seperately under pressure and to set up Turkish district north of the Island. 1974 interference is the turning point of the Turkey's history. Turks gained an area out of national agreement (Misak-i Milli) border. The date 1983 is a historical step against Greek cypriot who assumes Turks constantly as a minority. Greek goverment was the point of discussion with Turks who had been assumed not in equal statute so far moreover with the state who was not recognized except Turkey. The independence declaration of Turkish Republic of Northern Cyprus is genuine whether recognized or not and got its power from Turkish Republic and Turkish people. VI 187

NİTEL SİSTEM TANILAMA Yapay Zeka'nın nitel uslamlama alanındaki bu araştırmanın temel katkısı, nitel sistem tanılama algoritması QSI'in geliştirilmesidir. QSI'm girdisi, tanılanacak sistemin nitel davranışlarının bir betimlemesidir. Çıktısı bu davranışları gösteren sistemin Kuipers'in QSIM nitel benzetim algoritmasının biçeminde ve sistemin girdide belirtilmemiş `derin` parametrelerini de içerebilen bir kısıt modelidir. Nitel modellemeye QSI yaklaşımı sistem parametrelerinin `anlamları` hakkında hiç bir varsayım yapmaz ve bilgiye gereksinmez. QSI geniş biçimde tartışılmakta ve örneklenmektedir. Diğer katkılar, bir grup `sahte` QSIM davranışını elemek için yeni bir yöntem ve bir sonradan tahmin algoritmasıdır. Sahte davranışları azaltma konusuna başka yaklaşımların aksine, burada sunulan yöntem girdideki model hakkında kısıtlayıcı varsayımlar gerektirmez. Belli bir tür sahte davranışın saf QSIM'in model kısıtlan için kullanılan karşılık değer takımlarında sadece nokta değerlerin tutulması konusundaki İsrarı nedeniyle ortaya çıktığı saptanmıştır. Sunulan çözüm, verilen işletim örnekleri ve ispatların da gösterdiği gibi, algoritmanın genel karmaşıklığını kötüleştirmeden daha doğru çıktıların oluşmasını sağlar. Sonradan tahmin, değişim yasaları ve şimdiki durum verildiğinde olasıgeçmişleri bulma işidir. Algoritmayı elde etmek için, zamanın `geçişi` ile ilgili değişikliklerin yanısıra, benzetimce üretilen durum ağacını yorumlamanın farklı bir yöntemi getirilmiştir. Tanı uygulamaları için umut vaadeden bu uslamlama türüyle ilgili konular tartışılmıştır. IV QUALITATIVE SYSTEM IDENTIFICATION The main contribution of this research in the qualitative reasoning area of Artificial Intelligence is the development of the qualitative system identification algorithm QSI. QSI's input is a description of the qualitative behaviors of the system to be identified. Its output is a constraint model (possibly containing `deep` parameters absent in the input) of that system, in the format of Kuipers' qualitative simulation algorithm QSIM. The QSI approach to qualitative modeling makes no assumptions and requires no knowledge about the `meanings` of the system parameters. QSI is discussed in detail. Other contributions are a new method of eliminating a class of spurious QSIM predictions, and an algorithm for postdiction. Unlike other approaches to spurious behavior reduction, the method presented here does not require restricting assumptions about the input model. A particular kind of spurious behavior is shown to be caused by pure QSIM's insistence on assigning only point values to `corresponding value tuples` associated with model constraints. The solution put forward here preserves the overall complexity of the algorithm, while producing fewer incorrect predictions, as shown by the presented reports of the case runs and proofs. Postdiction is the task of finding out the possible pasts of the system underconsideration, given the laws of change and the current state. For obtaining the algorithm, a different scheme of interpreting the tree built by simulation is imposed, as well as the handling of the `flow` of time. Issues of this reasoning task, which is promising for diagnosis applications, are discussed. 161

Teknolojinin artan kullanımı hukuksal anlamda cevaplanması gereken pek çok so-ruyu da beraberinde getirmektedir. Botların çevrimiçi işlemleri de bunlardan biri haline gelmiştir. Özellikle, elektronik sözleşmelerin akdedilmesindeki kullanımları öğretisel anlamda tartışmalı bir konudur. Elektronik sözleşmeler internet siteleri, elektronik posta, mobil uygulamalar gibi yöntemlerle kurulabilmektedir. Botların bu yöntemlere dahil olması halinde ise başta sözleşme taraflarının kim olduğu, bot-lar aracılığıyla akdedilen sözleşmelerin hazırlar arasında olup olmadığı, gönderilen beyanların öneri mi öneriye davet mi olduğu, ayrıca söz konusu beyanların bağla-yıcılığı gibi hususlar sözleşmeler hukuku bakımından belirsizlikler yaratmaktadır.Öte yandan, botlar aracılığıyla akdedilen elektronik sözleşmelerin artan kullanımı-nın yarattığı bazı hukuksal sorunlara mevcut hukuk kuralları ile çözüm bulunabil-mektedir. Türkiye'deki düzenlemelere bakıldığında Elektronik Ticaretin Düzen-lenmesi Hakkında Kanun, Tüketicinin Korunması Hakkında Kanun ve Mesafeli Sözleşmeler Yönetmeliği bu açıdan göz önünde bulundurulabilir. Ancak mevcut düzenlemelerin yetersiz kalmaya başladığı teknolojik gelişmeler de söz konusudur. Çevrimiçi ortamda hızlı alım satım yapabilen botların tüketicilerin özellikle indirim-li ürünlere ulaşmasında mağduriyet yaşamasına sebep olabilmektedir. Türk Huku-ku'na büyük oranda etki eden Avrupa Birliği (AB) düzenlemeleri ve Türk Hukuku çerçevesinde botların elektronik sözleşmelerdeki kullanımına ancak geniş bir yo-rum yöntemiyle ulaşılmaktadır. Dolayısıyla botların kullanımıyla ilgili ilerleyen dönemlerde bir mevzuat çalışmasının söz konusu olması muhtemeldir. Henüz ge-lişmekte olan bir teknoloji olduğundan, bu alanda sert hukuk düzenlemesi yapmak yerine, yumuşak hukuk, eş düzenleme ve öz düzenleme gibi modellere yönelmek gerekebilir. AB kapsamındaki yaklaşımlar da gözetildiğinde, ilerleyen dönemlerde botlar konusunda özellikle tüketicinin korunmasına yönelik düzenlemelerin yapıl-ması gerekecektir. Bu sebeple, Türkiye'deki kanun koyucu da bunların paralelinde bir yol haritası izleyebilir. The increasing usage of technology brings along many questions that need to be answered in a legal manner. `Online transactions of the bots` has also become one of them. Especially the use on concluding electronic contracts is a controversial issue in the doctrinal sense. Electronic contracts can be concluded by methods like web sites, e-mail, mobile applications. The fact, that the bots are included in these methods, creates uncertainties in terms of contracts law such as: who the parties to the contract are, whether the contracts concluded are between the bots and availa-ble people, whether the declarations submitted are offer or call for offer, and the binding of the declarations.On the other hand, some legal problems caused by the increasing usage of elec-tronic contracts concluded by the bots can be solved by the existing legal rules. Referring to the regulations in Turkey, Law on the Regulating of Electronic Commerce, Law on Consumer Protection and The Directive on Distance Con-tracts can be taken into consideration in this respect. However, there are techno-logical developments to which the existing regulations are inadequate. It is possi-ble that the bots, which can be quickly traded online, can cause the consumers to be victimized especially when they attain discounted products. Within the frame-work of European Union (EU) regulations that have a profound effect on Turkish Law and of the Turkish Law itself, the usage of bots in electronic contracts is only reached through an extensive interpretation method. Therefore, it is likely that there will be a legislative work on the use of bots in the future. Since it is a devel-oping technology, it may be necessary to refer to models such as soft law, co-regulation, and self-regulation rather than hard law regulation in this field. Con-sidering the approaches within the scope of the EU, it will be necessary to regulate bots, especially for the protection of consumers, in the following periods. There-fore, the legislator in Turkey can follow a road map in parallel with them. 109

Kapalı Zamansı Eğriler üzerine tartışmalar, bu eğrileri kullanarak Turing Makinesi ile hesaplamaları daha efektif hale getiren hesaplama modellerine yol açmıştır. Bu modeller verileri zamanda geriye gönderme gücüne sahip olmalarından ötürü zamanın nedenselliğini bozarak paradokslara yol açabilmektedirler. Modeller kendi içlerinde bu paradoksların önüne geçmek için yaptıkları varsayımlarına göre farklılık göstermektedir. Farklı hesaplama modelleri üzerine çalışmaların karmaşıklık sınıfları ve bu sınıfların birbirleri ile olan etkileşimleri üzerine açıklık getirebildiği bilinmektedir.Hesaplama modellerinin ilki Deutsch tarafından önerilmiş olup, paradoks oluşma-sını engellemek için zamanda geri gönderilen bitlerin tek bir halde bulunmak yerine bir olasılık dağılımı içinde bulunduklarını varsaymaktadır. İkinci model Lloyd vd tarafından önerilmiştir ve istenilmeyen olasılık çıktılarının sonuç kümesinden çıkarılabilme gücüne sahiptir. Bu gücü ise makinenin her zaman kararlı olması ve makine ile etkileşim sonucu çıkabilecek paradoksların olma ihtimalinin sıfır olduğu varsayımı sayesinde elde etmektedir. Üçüncü model Say ve Yakaryılmaz tarafından önerilmiştir ve Deutsch'un modelini geliştirerek modelin birkaç dezavantajını ortadan kaldıran iyileştirmeler sunmaktadır.Bu tezde, kapalı zamansı eğriler tabanlı hesaplama modelleri incelenip bu modellerin NP-complete problemlere nasıl efektif çözümler getirdiği analiz edilmektedir. İkinci olarak literatürde geçen bu sınıfa ait bir algoritmanın aynı hatayı daha az devre masrafı ile elde edebilen bir versiyonu önerilmiştir. Son olarak Deutsch'un modeli ile hesaplamalarda ortaya çıkabilen bir durum üzerine tartışma ve analiz yer almaktadır. Discussions of Closed Timelike Curves (CTC) led to a few computation models that when used in conjunction with a Turing Machine, yield much more efficient computations. CTC assisted computation has the ability to send a piece of information back in time which breaks the time causality and has various paradoxes associated with it. Computation models deal with these paradoxes differently by making different assumptions. Regardless of the practicality of CTCs, studying different computation models has the possibility to grant valuable insight into complexity classes and their relationships among each other. The first of these models is proposed by Deutsch. The model avoids paradoxes by assuming that the states that enter and exit the machine constitute a probability distribution and that the machine outputs a stationary distribution. The second model, proposed by Lloyd et al. has the ability to discard unwanted outcomes, via the assumption of time-related paradoxes that can be caused by CTC interaction to be impossible. The third model, proposed by Say and Yakaryılmaz improves upon Deutsch's model and deals with some of its shortcomings.In this thesis, we demonstrate and analyze how these CTC based computation models help solve NP_complete, and some other problems efficiently and propose a more cost-efficient version of one such algorithm from the literature. Lastly, we explore and discuss some odd and interesting properties of calculations in DCTCs. 61

Literatürde ortaya sürülmüş olan pek çok makine, bir sonlu durumlu makinenin ek bir hafıza ünitesi ile güçlendirilmiş hali olarak düşünülebilir. Bu tezde, bu makine-/newline lerden ikisine, gruplar üzerinde tanımlı sonlu durumlu makinelere ve eve dönen vektör makinelerine odaklanılmıştır.$ G $ grubu üzerinde tanımlı bir makine, sahip olduğu ek hafıza ünitesinde $ G $ grubundan bir elemanı tutma hakkına sahip, belirlenimci olmayan bir sonlu durumlu makinedir. Başlangıçta hafıza ünitesinin değeri $ G $ grubunun birim elemanıdır. Bir hesaplamanın başarılı sayılabilmesi için hafıza ünitesinin değerinin, her adımda grubun bir elemanıyla çarpıldıktan sonra bitimde grubun birim elemanına eşit olması beklenir. Bu çalışmada tam sayılı ve rasyonel sayılı matris grupları üzerinde tanımlanan sonlu durumlu makine-/newline ler incelenmiş, bu makinelerin tanıdığı dil sınıflarının birbirleri ile olan ilişkileri ortaya çıkarılmıştır. Grubun büyüme hızı, makinelerin çalışma süresi gibi çeşitli parametrelere bakılarak, bu parametrelerin makinelerin tanıma gücünü nasıl etkilediği araştırılmıştır. Matris yarıgruplarının karar verme problemleri ile ilintili makinelerin karar verme problemleri arasında bir bağ kurulmuştur. Grup üzerinde tanımlı makinelerle yakından ilişkili olan bazı modeller incelenmiş ve bir takım yeni sonuçlar elde edilmiştir.Yeni tanımladığımız eve dönen vektör makinesi, bir sonlu durumlu makinenin bir vektörle güçlendirilmesi ve makineye bu vektörü her adımda bir matrisle çarpma hakkı verilmesiyle ortaya çıkmıştır. Makinenin vektörün başlangıç vektörüne eşit olup olmadığını kontrol etme hakkı vardır ve makinenin kabul şartı, hesaplama bittiğinde vektörün başlangıç vektörüne eşit olması ve kabul durumlarından birinde bulunulmasıdır. Kullanılan matris kümesi sınırlanarak ve vektörün eşitlik kontrolünün sadece en sonda gerçekleşmesine izin verilerek, farklı kısıtlamaların makineye olan etkisi incelenmiştir. Makinenin çeşitli sürümleri tanımlanarak, bu modellerin dil tanıma gücüyle klasik modellerin dil tanıma gücü karşılaştırılmıştır. Matris grupları üzerinde tanımlı sonlu durumlu makinelerle, bir yönlü belirlenimci olmayan kör eve dönen vektör maki-/newline neleri arasında ilişki kurularak eve dönen vektör makineleri ile ilgili yeni sonuçlar elde edilmiştir. Gerçek zamanlı eve dönen vektör makineleri üzerinde özellikle durulmuş, bazı kapalılık özellikleri gösterilmiş ve bu makinelerin tek durumlu versiyonları analiz edilmiştir. Stern-Brocot ağacından faydalanarak dizgeleri vektörlere kodlamaya yarayan bir metod geliştirilmiştir. Many of the numerous automaton models proposed in the literature can be regarded as a finite automaton equipped with an additional storage mechanism. In this thesis, we focus on two such models, namely the finite automata over groups and the homing vector automata.A finite automaton over a group $ G $ is a nondeterministic finite automaton equipped with a register that can hold an element of the group $ G $. Initially the register is initialized to the identity element of the group and a computation is successful if the register is equal to the identity element at the end of the computation after being multiplied with a group element at every step. We investigate the language recognition power of finite automata over integer and rational matrix groups and reveal new relationships between the language classes corresponding to these models. We look at various parameters such as the growth rate of the groups and the run-time of the machines, to discover the effects of these parameters on the language recognition power. We establish a link between the decision problems of matrix semigroups and the decision problems of corresponding automata. We look at some computational models which are closely related to finite automata over groups, namely the valence pushdown automata and the context-free valence grammars and present some new results.We also propose the new homing vector automaton model, which is a finite automaton equipped with a vector, and which can multiply this vector with an appropriate matrix at each step. The vector can be checked for equivalence to the initial vector and the acceptance criterion is ending up in an accept state with the value of the vector being equal to the initial vector. We examine the effect of various restrictions on the model by confining the matrices to a particular set and allowing the equivalence test only at the end of the computation. We define the different variants of the model and compare their language recognition power with that of the classical models. We establish a link between finite automata over matrix groups and one-way nondeterministic blind homing vector automata which extends our knowledge on the latter. We pay special attention to real-time homing vector automata and analyze their stateless versions and closure properties. We develop a method for encoding strings into vectors, based on the Stern-Brocot Tree, which may be of independent interest. 162

Öğüt, bir hesaplama aygıtına bu aygıtın gücünü kendi sınırlarının ötesinde genişle-terek hesaplamasına yardım etmek için sağlanan dış kaynaklı güvenilir bir bilgi parçası-dır. Hesaplanabilir olma kısıtlaması olmayan bu yardımın içeriği tipik olarak yalnızca aygıtın gerçek girdisinin boyutuna bağlıdır ve girdinin esas içeriğinden bağımsızdır. Öğüt alan hesaplamanın özellikleri çeşitli hesaplama modelleri baz alınarak ve karmaşık-lık, çok biçimli hesaplama, formel diller ve sözde rastgelelik gibi farklı kavramlar ile bağlantılı biçimde çalışılagelmiştir. Sonlu durumlu makinalara bu türden harici yardım sağlamak için geliştirilen birkaç model de çeşitli gruplar tarafından çalışılmıştır.Bu araştırma kapsamında iki yeni öğüt alan sonlu durumlu makine modeli tanım-landı: öğüt şeritli sonlu durumlu makineler ve işaretle öğüt alan sonlu durumlu makine-ler. İlk modelde öğüt, bir dizi şeklinde ve girdi şeridinden bağımsız olarak erişilebilen ayrı bir şerit üzerinde sağlanır. İkinci modelde ise öğüt, girdi şeridi üzerine konulan ve iz adı verilen tek biçimli işaretler aracılığı ile sağlanmaktadır. Bu modellerin her birinin hesaplama gücü ve sınırları, temel hesaplama modelinin belirlenimci, olasılıksal ya da kuantum olmasına ve öğütün belirlenimci ya da rastgele biçimde seçilmesine bağlı olarak değişen çeşitli durumlarda incelendi. Artan öğüt miktarının bir hesaplama kaynağı olarak etkileri çeşitli biçimlerde değerlendirmeye dahil edildi. Her bir modelin versiyonları dil tanıma güçleri açısından, kendi aralarında ve daha önceden çalışılmış benzer makine modelleri ile karşılaştırıldı. Bu incelemenin temel sonuçları olarak söz konusu modeller tarafından değişik durumlarda tanınabilen dil sınıfları arasındaki çeşitli ayrışma, örtüşme ve sonsuz sıradüzen ilişkilerinin varlığı gösterildi. Advice is a piece of trusted supplemental information that is provided to a computing device, in advance of its execution in order to extend its power beyond its limits and hence to assist it in its task. The content of this assistance, which is not restricted to be computable, typically depends only on the length, and not the full content of the actual input to the device. Advised computation has been studied on various computational models and in relation with concepts as diverse as complexity, nonuniform computation, formal languages and pseudorandomness. Several models for providing such external assistance to finite automata have also been studied by various groups. In this research, we introduce two novel models of advised finite automata: finite automata with advice tapes and finite automata with advice inkdots. In the former model advice is provided in the form of a string which is placed on a separate tape accessible independently from the input. In the latter one, we model advice as a set of uniform marks placed on the input tape which are called inkdots. We examine the power and limits of each of these models in a variety of settings where the underlying model of computation is deterministic, probabilistic or quantum and the advice is deterministically or randomly chosen. The roles of increasing amounts of advice as a computational resource are taken into consideration in various forms. The variants of each model are compared with each other and with the previously studied models of advised finite automata in terms of language recognition power. The main results of this analysis are demonstrated by establishing various separations, collapses and infinite hierarchies of the language classes that can be recognized with different models in varying settings. 126

Sonlu özdevinir ya da sonlu durum makinesi, bilgisayımda kullanılan matematiksel bir modeldir ve özdevinir teorisinde en çok çalışılan modellerden biridir. Yıllar boyunca deterministik, nondeterministik, olasılıksal ve kuantum özdevinir gibi sonlu durum makinelerinin birçok farklı çeşidi önerilmiştir. Ayrıca, bu özdevinir modellerinin birbirleri arasındaki ilişkileri ve biçimsel dillerle olan bağları üzerine ayrıntılı çalışmalar yapılmıştır.Bu tezde, özdevinir modellerinde özlülük özelliği üzerine çözümlemeler yapılmıştır. Konu kapsamı, üç ana başlık altında ayrıntılandırılmıştır. İlk olarak, çeşitli sonlu makine modellerinin deterministik özdevinirler tarafından simüle edilmesi konusunda yapılan çalışmalar yer almıştır. İkinci olarak, üç düzenli dil ailesi tanımlanmış ve bu dil ailelerinin farklı özdevinir modelleri tarafından en az kaç durum ile tanınacağı gösterilmiştir. Üçüncü olarak, tek harfli alfabeler kullanılarak yaratılabilecek düzenli dilleri ve bu dilleri tanıyan sonlu makineleri birlikte tanımlayan bir biçim geliştirilmiştir. Adı, `Tekli Sonlu Periyodik Biçim` olan bu form kullanılarak düzenli dillerin kapalılık özellikleri üzerine detaylıca çalışılmıştır. Finite state automaton, or finite automaton, is a mathematical model of computation and has been one of the most studied models in automata theory. Throughout the years, many different types of finite state automata are proposed, such as deterministic, nondeterministic, probabilistic, and quantum automata. Furthermore, the important questions that how they are related to each other, and how they are related to formal languages, have been a subject of intensive research.In this thesis, we study the succinctness properties of various finite automata. First, we thoroughly study the topic of simulating various finite automata by deterministic finite automata. Second, we work with three different families of regular languages and we provide the various minimal automata (i.e. minimal in the sense of the number of states used) deciding them. Third, we provide a descriptive form called `Unary Finite Periodic Form`, or shortly UFPF, to efficiently describe regular languages over unary alphabets and we introduce algorithms to show the efficient realization of closure properties of UFPF. 126

Bu çalışmada, ayrık olasılık dağılımının entropisinin toplanır hata payıyla kestirimi iki farklı kurguda irdelenmektedir. Buna göre bilinmeyen bir olasılık dağılımı p'ye erişim iki farklı sorgu türüyle sağlanmaktadır. Herhangi bir girdisi olmayan SAMP sorgusu p[x] olasılığıyla x döndürmektedir. Girdi olarak x alan PMF sorgusunun ise çıktısı p[x]'dir. SAMP modeli ismini verdiğimiz ilk kurguda p ile sadece SAMP sorgusu vasıtasıyla iletişim sağlanmaktadır. SAMP+PMF modeli olarak adlandırdığımız ikinci kurgudaysa hem SAMP hem de PMF sorguları kullanılabilmektedir.Daha kesin bir ifadeyle, çalışmanın odak noktası olasılık dağılımı p'nin entropisinin yüksek ihtimalle toplanır hata payıyla kestirimi problemidir. Shannon entropisinin kestirimini incelediğimiz bölümde Valiant ve Valiant'ın SAMP modelinde göstermiş olduğu eşleşen alt ve üst sınırları ve Canonne ve Rubinfeld'in SAMP+PMF modelinde inşa etmiş olduğu algoritmayı tasvir ediyoruz. Renyi entropisini incelediğimiz bölümdeyse Acharya ve diğerleri tarafından sunulan üç farklı eşleşen alt ve üst sınır çiftini analiz ediyoruz.Kendi katkımız olarak, önce SAMP+PMF modelinde Shannon entropisinin kestirimi probleminin en az poli-logaritmik sayıda sorgu gerektirdiğini kanıtlayarak Canonne ve Rubinfeld'in sunduğu üst sınırın optimal olduğunu gösteriyoruz. İkinci olarak, yine SAMP+PMF modelinde Renyi entropisinin kestirimi probleminin eşleşen üst ve alt sınırlarını inşa ediyoruz. We investigate the query complexity of additively estimating entropy of a discrete probability distribution in two settings. Let p be an unknown probability distribution on [n]:= {1, 2, ..., n}, and define two kinds of queries: A SAMP query takes no input and returns x with probability p[x]; a PMF query takes as input x and returns the value p[x]. In the SAMP model of query complexity, the only allowed interaction with p is via SAMP queries. In the SAMP+PMF model, both SAMP andPMF queries are utilized to interact with p.In particular, we consider the task of estimating the entropy of a probability distribution. For the usual Shannon entropy, we review the matching upper and lower bounds established by Valiant and Valiant in the SAMP model, and describe the algorithm constructed by Canonne and Rubinfeld in the SAMP+PMF model. For the Renyi entropy, we analyze three different matching upper and lower bound pairs introduced by Acharya et al. in the SAMP model.We show that at least poly-logarithmic number of queries are necessary to estimate the Shannon entropy in the SAMP+PMF model, matching a recent upper bound of Canonne and Rubinfeld. In addition, we prove matching upper and lower bounds to estimate the Renyi entropy in the SAMP+PMF model. 71

Bu tezde ispatçı ve çürütücü adlı iki oyuncunun girdinin dil içinde olup olmadığı üzerine oluşturduğu diyoloğun sınırlı kaynaklı olasılıksal bir hakem tarafından okunduğu yeni bir münazara modeli tanımlanmaktadır. Modelimiz tek yönlü etkileşimli ispat sistemleri, noksan bilgili oyunlar ve olasılıksal kontrollü münazara modellerini birleştirir ve genelleştirir. Tam-, kısmi- ve sıfır-bilgili münazara çeşitleri ele alınmaktadır. Kısmi- ve sıfır-bilgili münazaralarda ispatçı çürütücünün mesajlarından sırayla bazılarını ve hiçbirini göremezken, tam-bilgili münazaralarda her iki oyuncu da birbirlerinin mesajlarını tamamen görürler. Zamansal, belleksel ve olasılıksal olarak sınırlı bir hakemin bu çeşitlerde münzaraları kontrol ederek hangi dil ailelerini tanıyabileceği araştırılmaktadır. O(1) bellek ve O(1) rastgelelik kullanan hakemlerin bu üç münazara çeşidi için tanıyabildiği dil sınıflarının tam tanımı yapılmaktadır. İlaveten, sonlu bellekli hakemler tarafından herhangi bir hata payı ile kontrol edilebilen sırasıyla sıfır- ve kısmi-bilgili münazaralara sahip diller kümesi için alt limitler verilmektedir. Tam- ve kısmi-bilgili münazaraların zaman-sınırlı hakemler tarafından kontrol edildiği durumun gücü de araştırıldı ve bu hakemlerin ne kadar rastgelelik kullanırlarsa kullansınlar aynı sınırlara sahip belirlenimci hakemlere bir üstünlük kuramadıkları anlaşıldı. Fakat, rastgelelik kullanılmasının bu zaman-sınırlı hakemlerin beleklerinin zaman-sınırının logaritmasına kadar indirilebilmesine izin verdiği ortaya çıktı. Ayrıca, polinom zaman ve logaritmik bellekle sınırlı hakemlerin PSPACE'teki diller için tam- ve kısmi-bilgili münazara kontrol etmesinin logaritmik rastgelelik kullanılarak da mümkün olduğu gösterilmektedir. Son olarak, polinom zaman ve logaritmik bellek kullanıp tam-bilgili münazara kontrol eden hakemlerin yapısından faydalanıp böyle münazaralara sahip dillerin nicellendirilmiş matrisler üzerinde maksimum çarpım problemine indirgenebileceği gösterilerek bu problemin yakınsanamazlığı ile ilgili bir sonuç sunulmaktadır. We introduce a model of probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. Our model combines and generalizes the concepts of one-way interactive proof systems, games of incomplete information, and probabilistically checkable complete-information debate systems. We consider debates of partial- and zero-information, where the prover is prevented from seeing some or all of the messages of the refuter, as well as those of complete-information. The classes of languages with debates checkable by verifiers operating under severe bounds on the time, memory, and randomness are studied. We give full characterizations of versions of these classes corresponding to simultaneous bounds of O(1) space and O(1) random bits, and logarithmic space and O(1) random bits. We further examine the power of constant-space model by giving lower bounds for the classes of languages checkable by such verifiers for any desired error bound when we loosen the randomness bound. We also examine the power of debate checkingby time-bounded verifiers and show that no amount of randomness can help a time-bounded verifier to outperform its deterministic counterpart. However, we show that randomness does seem to help when we further constrain these time-bounded verifiers to use only logarithmic space in the order of their time bound. Additionally, in case of logspace and polynomial-time verifiers, we show that logarithmic randomness is sufficient to check complete- and partial-information debates for the languages in PSPACE. Finally, we show that any language having debates checkable by logspace polynomial-time verifiers can be reduced to the quantified max word problem for matrices, which allows us to present a result on the hardness of approximating this problem. 73

Bu tezde genel kuantum operatörlerini destekleyen yeni bir kuantum Turing makine modeli ile birlikteonun yığıt-bellekli, sayaçlı ve sonlu bellekli modelleri tanımlandı ve az belleğe sahipklasik ve kuantum makinelerin hesaplama güçleri bir çok durum için incelendi.Temel katkılarımız aşağıda özetlenmiştir.İlk olarak kuantum Turing makineleri sınırlı olmayan hata açısından ele alındı:(i) logaritma-altı bellek kullanılan bazı durumlarda hesaplama gücü açısındankuantum Turing makinelerinin klasik muadillerinden üstün olduğu gösterildi;(ii) aynı sonuç sonlu belleğe sahip kısıtlı kuantum Turing makineleri için de elde edildi;(iii) gerçek-zamanlı sonlu belleğe sahip belirlenimci olmayan kuantum Turing makinelerinintanıdığı dil ailesi belirlendi.İkinci olarak, sonlu belleğe sahip kuantum Turing makineleri sınırlı hata açısından ele alındı:(i) sola gitme veya durma hakkı yasaklanmış fakat kendisini başlangıç noktasına taşıyabilenözel kafaya sahip yeni çift-yönlü kuantum ve olasılıksal sonlu durumlu makineler tanımlandı;(ii) hesaplama gücü açısından bu tür kuantum makinelerin olasılıksal olanlardan daha güçlü olduğu gösterildi;(iii) bu modeller temelinde, çift-yönlü olasıksal ve klasik kafaya sahip kuantum sonlu durum makinelerin,çift-yönlü belirlenimci olmayan sonlu durum makineler ile kendi tek-yönlü muadillerindendaha az sonlu bellek kullandıkları gösterildi;(iv) ayrıca olasılıksal ve kuantum sonseçimli sonlu durumlu makineler ile sınırlı hata payıile tanıdıkları dil sınıfları tanımlandı ve bir çok özellikleri gösterildi.Üçüncü olarak, sadece yazma hakkı olan bir hafıza eklenen gerçek-zamanlı kuantum sonlu durumlumakenelerin hesaplama gücü, farklı türdeki sayaçlı makineler üzerinden yapılan bir çok benzetim ile incelendi.Paralel olarak, sayaçlı ve yığıt-bellekli makinelere dair bazı sonuçlar elde edildi.Son olarak, literatürde geçen bazı alt sınırların,düzenli olmayan bir dili tanıyan gerçek-zamanlı klasik Turing makineler için mümkün olan en iyi sınırlar olduklarıgösterildi.Ek olarak, benzer soru diğer tür gerçek-zamanlı makineler için araştırıldı veonlar tarafından az bellek ile tanınan birçok düzenli olmayan dilin varlığı gösterildi. In this thesis, we introduce a new quantum Turing machine model that supportsgeneral quantum operators, together with its pushdown, counter, and finite automaton variants,and examine the computational power of classical and quantum machines using small space boundsin many different cases. The main contributions are summarized below.Firstly, we consider quantum Turing machines in the unbounded error setting:(i) in some cases of sublogarithmic space bounds, the class of languages recognized by quantum Turing machinesis shown to be strictly larger than that of classical ones;(ii) in constant space bounds, the same result can still be obtained for restricted quantum Turing machines;(iii) the complete characterization of the class of languages recognized byrealtime constant space nondeterministic quantum Turing machines is given.Secondly, we consider constant space-bounded quantum Turing machines in the bounded error setting:(i) we introduce a new type of quantum and probabilistic finite automatawith a special two-way input head which is not allowedto be stationary or move to the left but has the capability to reset itselfto its starting position;(ii) the computational power of this type of quantum machineis shown to be superior to that of the probabilistic machine;(iii) based on these models, two-way probabilistic and two-way classical-head quantumfinite automata are shown to be more succinct than two-way nondeterministic finite automataand their one-way variants;(iv) we also introduce probabilistic and quantum finite automata with postselection with theirbounded error language classes, and give many characterizations of them.Thirdly, the computational power of realtime quantum finite automata augmented with awrite-only memory is investigated by showing many simulation results for different kinds of counter automata.Parallelly, some results on counter and pushdown automata are obtained.Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular languageare shown to be tight. Moreover, the same question is investigated for some other kinds of realtime machines andseveral nonregular languages recognized by them in small space bounds are presented. 184

Nitel benzetimciler, dinamik sistemlerin olası davranışlarının analizi konusundaönemli araçlardır. Nitel benzetim yönteminin bazı kuramsal sınırlarımevcuttur. Bir nitel benzetimci, kimi girdiler için ya yanlış tahminler vermekteya da bazı olası davranışları göstermemektedir. Gösterilmiştir ki,mükemmel bir nitel benzetimci yapılamaz. Çünkü bazı yanlış tahminlerinyanlış olduğu ispatlanamamaktadır.Bu tez, yanlışlığı ispatlanabilen bütün yanlış tahminleri fark edip eleyebilenbir nitel benzetimcinin yapılabilirliğini sorgulamaktadır. Olumsuz birsonuca ulaşılmıştır. Kimi makul özellikleri taşıyan herhangi bir nitel benzetimciiçin bu nitel benzetimci tarafından elenemeyen yanlışlığı ispatlanabilirbir yanlış tahmine neden olan ve sistematik bir şekilde elde edilebilen birgirdi mevcuttur.Bunun yanı sıra, gösterilmiştir ki yanlışlığının ispatlanması üstel zamangerektiren yanlış tahminler de bulunmaktadır. Qualitative simulators are important tools for analyzing the possible behaviorsof a dynamical system. The technique of qualitative simulation hassome theoretical limitations. For some input system models, a qualitativesimulator either predicts spurious (impossible) behaviors or does not predictsome possible behaviors. It has been shown that a ?perfect? qualitativesimulator cannot be built, because there are some spurious behaviors whichcannot be proven to be spurious.This thesis questions the possibility of building a qualitative simulatorwhich can detect and eliminate all spurious behaviors which can be provento be so. We find the answer to be negative. For each qualitative simulatorwhich possesses some reasonable properties, there is an efficiently constructible,provably inconsistent input which cannot be rejected by the simulatorin question.In addition, it is shown that there exist spurious behaviors which requireexponential time to detect. 45

Fiziksel bir dizgede değişkenlerin gelecekteki sayısal davranışı o dizge-gs sye ait adi diferansiyel denklem takımı tarafından belirlenir. Bu denklemtakımındaki sayısal büyüklüklerin kaldırılması ile elde edilen nitel diferansiyeluu udenklem sistemi ise adi denklem sisteminin yalnızca yapısını ifade eder. Birnitel denklem sistemi, dizgedeki değişkenlerin davranışlarının üngürülmesinings s o oudeğişkenlerin gelecekteki sayısal değerlerinin bulunmasından daha ünemligs g oolduğu durumlarda şok kullanışlıdır. Nitel denklem sistemleri aynı zamandag c snitel model olarak adlandırılır. Bir nitel modeldeki ilişkiler, değişkenlerdens gsbirisinin değerindeki bir değişimin dizgedeki diğer değişkenleri nasıl etkileye-g gs g gsceğini incelemek işin kullanılabilir. Diğer bir deyişle, nitel modeller diz-g c g sgenin bizce güzlemlenen davranışına neden olan arkaplandaki mekanizmanıno sanlaşılmasına yardımcı olurlar.sNitel modelleri sıfırdan yazmak kolay değildir ve alanında bilgi sahibi birguzman tarafından yapılması gerekir. Nitel modellerin güzlemlerden otomatikoolarak üğrenilmesi daha da zordur ve otomatik üğrenme alanındaki problem-og oglerden bir tanesidir. Tezde bu problemin şüzümüne yünelik olarak LYQUIDco u u oadı verilen bir algoritma ünerilmektedir. Algoritma güzlemlenmiş sayısalo o sürneklerin uzerine polinom eğriler oturtarak ürnekleri oluşturan gerşek fonksi-o ü g o s cyonlara yaklaşıklıklar bulmaktadır; değişkenler arasındaki nitel ilişkilerin bu-s gs slunmasında ise esas ürnekler yerine bu polinomlar kullanılır. LYQUID'inoyazındaki denektaşı problemleri uzerinde başarılı sonuşlar veren, hızlı ves ü s cgürültüye toleransı yüksek olan bir algoritma olduğu güsterilmiştir. Algo-uu u u go sritma, ürneklemenin nasıl yapıldığı ile ilgili kısıtlamaları kaldırmanın ütesindeo g odeğişkenlerin belli zaman aralıklarında ürneklenmediği durumlarda da başarılıgs o g solabilmektedir.1 The set of ordinary diï¬erential equations (ODE) of a physical system de-termines the precise numerical behavior that will be exhibited in the future.Abstracting an ODE into a qualitative diï¬erential equation (QDE) systemremoves all quantities from the equations and leaves only the structure of theequation system intact. However, a QDE is still very useful in anticipatingthe future when the qualitative behavior of the system is important ratherthan the exact numerical solution. Another name for a QDE is a qualitativemodel. Qualitative relationships make up a qualitative model and it is possi-ble to analyze how a change in one of the variables in the system aï¬ects theother variables using these relationships. In other words, qualitative modelshelp us understand the underlying mechanism which determines the behaviorthat we observe.Writing qualitative models from scratch is a diï¬cult problem which needsto be done by an intelligent expert with domain speciï¬c knowledge. Automat-ing the discovery of qualitative models from observations is a diï¬cult problemof machine learning. Various algorithms have been proposed for the solutionof this problem in the literature. This thesis presents a new algorithm calledLYQUID for the solution of the same problem. The algorithm uses polyno-mials ï¬tted on observed numerical data as approximations to the underlyingreal world functions; discovery of qualitative relationships is then performedover those polynomials rather than the original data samples. LYQUID isshown to be a fast and successful learning algorithm which performs verywell on benchmark models and tolerates high levels of noise. The algorithmnot only relaxes the restrictions over how the data are sampled but it is alsocapable of working with missing data.1 86