BOUN Repository :: Browsing by Author "Say, Ahmet Celal Cem."

Browsing by Author "Say, Ahmet Celal Cem."

Now showing 1 - 20 of 24

A linguistically motivated information retrieval system for Turkish
(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2004., 2004.) Pembe, Fatma Canan.; Say, Ahmet Celal Cem.
Information retrieval (IR) has become an important application in today's computer world because of the great increase in the amount of web-based documents and the widespread use of the Internet. However, the classical "bag of words" approach no longer meets user expectations adequately. In this context, the use of natural language processing (NLP) techniques comes into mind. In this thesis, we investigate the question of whether NLP techniques can improve the effectiveness of information retrieval in Turkish. We implemented a linguistically motivated information retrieval system, called TURNA (TUrkish information Retrieval engine based on Natural language Analysis). The system uses knowledge of three different levels of natural language processing in document and query processing: morphological, syntactical and lexico-semantical levels. Different combinations of these NLP techniques are tested on a set of Turkish documents and queries. The results are evaluated in terms of precision and recall. It is shown that natural language processing techniques, especially stemming and the use of syntactical head-modifier pairs, can improve information retrieval effectiveness in Turkish.
An lexicon for idiomatic compounds in Turkish
(Thesis (M.A.)-Bogazici University. Institute for Graduate Studies in Social Sciences, 2007., 2007.) Eyigöz, Kadriye Elif.; Demiralp, Mine Nakipoğlu.; Say, Ahmet Celal Cem.
This work presents and comprises a constraint-based case-frame lexicon for idiomatic compounds headed by verbs in Turkish. The lexicon covers ten Turkish verbs with the highest number of senses to be used in natural language processing applications for representing and resolving senses of idiomatic compounds. This thesis gives detailed instructions, suggests conventions and describes a structure for organizing the data in the lexicon. It also provides a sample lexicon for ten verbs organized according to the structure proposed, in order to form a guideline for future lexicographic work based on this study.
Blind spots of qualitative simulators
(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2007., 2007.) Taşdemir, Nuri.; Say, Ahmet Celal Cem.
Qualitative simulators are important tools for analyzing the possible behaviors of a dynamical system. The technique of qualitative simulation has some theoretical limitations. For some input system models, a qualitative simulator either predicts spurious (impossible) behaviors or does not predict some possible behaviors. It has been shown that a “perfect” qualitative simulator cannot be built, because there are some spurious behaviors which cannot be proven to be spurious. This thesis questions the possibility of building a qualitative simulator which can detect and eliminate all spurious behaviors which can be proven to be so. We find the answer to be negative. For each qualitative simulator which possesses some reasonable properties, there is an efficiently constructible, provably inconsistent input which cannot be rejected by the simulator in question. In addition, it is shown that there exist spurious behaviors which require exponential time to detect.
Classical and quantum computation with small space bounds
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2011., 2011.) Yakaryılmaz, Abuzer.; Say, Ahmet Celal Cem.
In this thesis, we introduce a new quantum Turing machine model that supports general quantum operators, together with its pushdown, counter, and nite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many di erent 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 machines is 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 by realtime 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 nite automata with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way probabilistic and two-way classical-head quantum nite automata are shown to be more succinct than two-way nondeterministic nite automata and their one-way variants; (iv) we also introduce probabilistic and quantum nite automata with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime quantum nite automata augmented with a write-only memory is investigated by showing many simulation results for di erent 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 language are shown to be tight. Moreover, the same question is investigated for some other kinds of realtime machines and several nonregular languages recognized by them in small space bounds are presented.
Computability-theoretic limitations of qualitative simulation
(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2005., 2005.) Yılmaz, Özgür.; Say, Ahmet Celal Cem.
Qualitative reasoning and simulation are useful mathematical tools, especially for theanalysis, design and diagnosis of dynamic systems. Simulators which are seen to beincomplete, that is, which produce spurious predictions for a particular input, are usually augmented with additional filters eliminating that behaviour. Kuipers introduced asimulator (QSIM) which has the soundness property, that is, no trajectory which is thesolution of a concrete equation matching the input can be missing from the output. It hasbeen proven that there does not exist a sound and complete simulator whose input and output vocabularies are identical to those of the "pure" QSIM.This thesis contains a series of further results about computability-theoreticlimitations of qualitative simulation. Firstly, it demonstrates a method for modeling andsimulating an arbitrary Unlimited Register Machine (URM) using QSIM, and thereby establishes that qualitative simulation has universal computational power. By making useof reductions from the famous undecidable Halting Problem for computation toolspossessing universal computational power, it proves that it is impossible to build a soundand complete qualitative simulator using the QSIM representation for input and output for several "weakened" versions of the representation. It finishes with an ultimate result thatachieving a sound and complete simulator, which operates only in a single operating regionin which continuity rules are fully obeyed, is impossible,. The results in this thesis are demonstrated using the QSIM representation for inputand output, and are valid for all qualitative simulators whose input and output vocabulariesare identical to that of QSIM. They are important in the sense that they provide deeperinsight to the causes of spurious predictions, and they are also interesting for researchersaiming to construct provably sound and complete simulators using weaker representations.
Computation with chained Closed Timelike Curves
(Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019.) Çıkla, Mert Can.; Say, Ahmet Celal Cem.
Discussions of Closed Timelike Curves (CTC) led to a few computation models that when used in conjunction with a Turing Machine, yield much more eﬃcient com putations. 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 diﬀerently by making diﬀerent assumptions. Regardless of the practicality of CTCs, studying diﬀerent computation models has the possibility to grant valuable insight into complexity classes and their relationships among each other. The ﬁrst of these models is proposed by Deutsch. The model avoids paradoxes by assuming that the states that enter and exit the machine constitute a probabil ity 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 eﬃciently and propose a more cost-eﬃcient version of one such algorithm from the literature. Lastly, we explore and discuss some odd and interesting properties of calculations in DCTCs.
Constant-space, constant-randomness verifiers with arbitrarily small strong error
(Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020., 2020.) Gezer, Mehmet Utkan.; Say, Ahmet Celal Cem.
We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers are restricted to toss some fixed nonzero number of coins regardless of the input size. Say and Yakaryılmaz showed that the class of languages that could be verified by these machines within a strong error bound strictly less than 1/2 is precisely NL, but their construction yields verifiers with strong error bounds that are very close to 1/2 for most languages in that class. We characterize a subset of NL for which verification with arbitrarily low strong error is possible by these extremely weak machines. It turns out that, for any " > 0, one can construct a constant-coin, constant-space verifier operating within strong error " for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa(k)). We discuss why it is difficult to generalize this method to all of NL, and give a reasonably tight way to relate the power of lineartime 2nfa(k)’s to simultaneous time-space complexity classes defined in terms of Turing machines.
Design and simulation of two-way quantum finite automata
(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2006., 2006.) Atak, Fatih Mehmet.; Say, Ahmet Celal Cem.
In this thesis, we review classical finite state automata, (FSAs and TWAs) and 2- way quantum finite state automata (2QFAs). We examine fundamental theorems and their proofs. We develop a software simulator of quantum finite state automata. We introduce the simulator and by the help of the simulator, we examine some non-regular languages like {0n1n n > 0} (type 2) and {0n1n2n n > 0} (type 1). We also propose a new technique to enhance the language recognition probability of 2QFAs. This method may allow some languages to be recognized with bounded error, if we have an algorithm for the unbounded error version. A sample construction for such a case is inspected in detail. Using this technique, we enhance the complexity of a 2QFA which originally recognize string s with error probability of 1/2, beyond a well known 2QFA in the literature for the same language.
Efficient two-way quantum finite state automata
(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2007., 2007.) Yakaryılmaz, Abuzer.; Say, Ahmet Celal Cem.
The discovery of quantum algorithms which are exponentially more e fficient than the best known classical algorithms for similar tasks has spurred researchers to compare the relative powers of the classical and quantum versions of several computational models to better understand the causes and limitations of the apparent power of quantum computing. One model for which such comparative analyses have led to interesting results is that of nite automata. Among the various types of quantum nite automata, we concentrate on the strongest family, namely, two{way quantum nite automata (2qfa's). Kondacs and Watrous proved that 2qfa's are more powerful than their classical counterparts by describing a method for constructing 2qfa's that recognize the non{regular language Leq = fanbnj n > 0g for any given error bound > 0. Machines built according to this method have O(( 1 )2) states, and they halt after O(( 1 )jwj) steps, where w is the input string. In this thesis, we examine ways of reducing the dependence of these cost functions on the desired error bound. We present more e cient constructions to recognize the same language. One of our methods produces machines which halt in O(jwj) time (i.e. the running time does not depend on the error bound) and which have O(( 1 ) 2 c ) states for any given constant c > 1. Other methods, yielding machines whose state complexities are polylogarithmic in 1 , and which halt in O(log( 1 )jwj) time, are also presented..
Extended models of finite automata
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019.) Salehi, Özlem.; Say, Ahmet Celal Cem.
Many of the numerous automaton models proposed in the literature can be regarded as a nite automaton equipped with an additional storage mechanism. In this thesis, we focus on two such models, namely the nite automata over groups and the homing vector automata. A nite automaton over a group G is a nondeterministic nite automaton equipped with a register that holds an element of the group G. 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 nite automata over integer and rational matrix groups and reveal new relationships between the language classes corresponding to these models. We examine the e ect of various parameters on the language recognition power. We establish a link between the decision problems of matrix semigroups and the corresponding automata. We present some new results about valence pushdown automata and context-free valence grammars. We also propose the new homing vector automaton model, which is a nite automaton equipped with a vector that can be multiplied with a 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 e ect of various restrictions on the model by con ning the matrices to a particular set and allowing the equivalence test only at the end of the computation. We de ne the di erent variants of the model and compare their language recognition power with that of the classical models.
Finite and small - space automata with advice
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018., 2018.) Küçük, Uğur.; Say, Ahmet Celal Cem.
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 ﬁnite automata have also been studied by various groups. In this research, we introduce two novel models of advised ﬁnite automata: ﬁnite automata with advice tapes and ﬁnite 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 ﬁnite automata in terms of language recognition power. The main results of this analysis are demonstrated by establishing various separations, collapses and inﬁnite hierarchies of the language classes that can be recognized with diﬀerent models in varying settings.
Generalizations of hidden subgroup algorithms
(Thesis (M.S)-Bogazici University.Institute for Graduate Studies in Science and Engineering, 2005., 2005.) Poslu, Damla.; Say, Ahmet Celal Cem.
In the future, it can be possible to store bit information in atoms. In thatcase, classical mechanics will not be enough to explain the atomic level model. Instead quantum mechanics will have to be used. A quantum bit exists as a superpositionof 0 and 1. Creating superpositions and making parallel computation on them willallow faster solutions than classical computation. The field of quantum computationexamines the possibility of using these physical properties for solving computationalproperties more e±ciently.In this thesis, we consider the problem of generalizing some quantum algorithmsso that they will work on input domains whose cardinality is not necessarily powersof two. When analyzing the algorithms we assume that generating superpositions ofarbitrary subsets of basis states whose cardinalities are not necessarily powers of twoperfectly is possible. We have taken Ballhysa's model as a template and have extendedit to Chi, Kim and Lee's generalization of the Deutsch-Jozsa algorithm and to Simon'salgorithm.
Improved handling of SMS messages with statistical natural language processing techniques
(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2005., 2005.) Yıldırım, Ömer.; Say, Ahmet Celal Cem.; Arslan, Levent M.
The Short Messaging Service (SMS) is built on the ability of mobile telephones tosend and receive text messages. SMS based applications are increasing dramatically day byday in the telecommunications industry. The most common use of SMS is for notifying mobile phone users that they have new voice or fax mail messages waiting. Whenever anew message is dispatched into the mailbox, an alert by SMS informs the user of this fact.The Short Message Service can also be used to deliver a wide range of information tomobile phone users from share prices, match scores, weather, flight information, news headlines, lottery results, jokes. In general, user interaction based SMS services requestsome predefined keywords from the users and respond to them after processing theirmessages.However, most users think that they are communicating not with a machine but withhumans, so they compose misspelled and/or machine specific messages containing more than just the needed keywords. As a result, they receive error messages from the server andgenerally do not continue to use the software after trying two or three times by makingsame mistakes. In this thesis, I introduce a new Short Message Service (SMS) parsing model usingStatistical NLP Techniques, whose aim is to solve the existing SMS user subscriptionproblem of a real software company. To do this, the N-Gram statistical approach will beused.
Optimization of quantum random walk simulations
(Thesis (M.S)-Bogazici University.Institute for Graduate Studies in Science and Engineering, 2005., 2005.) Küçük, Uğur.; Say, Ahmet Celal Cem.
In computer science, an exponential performance gain is considered an importantachievement that can extend the set of practically computable problems. Behind the interest in quantum computation, there is the fact that several quantum algorithms have been shown toprovide exponential speedup against their classical counterparts. Of these, the most recent one,the one based on quantum random walks, is discussed in this work. The methods used indemonstrating the exponential algorithmic speedup by quantum random walks are analyzed indetail. This analysis comes after introductory parts where basic quantum computation concepts, quantum simulation techniques and quantum random walk ideas are discussed. Anew optimization technique on the implementation of quantum random walks is alsointroduced. This technique is based on the idea of manipulating the order in which theconstituent Hamiltonians are simulated for small durations in the iterative step of the simulation algorithm. Our approach can be generalized to optimize any quantum simulation inwhich the linear combination rule is used to simulate a collection of constituent Hamiltonians.
Problems of adiabatic quantum program design
(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2006., 2006.) Khusnitdinova, Evgeniya.; Say, Ahmet Celal Cem.
Although several quantum programming languages have already been proposed, none of these are based on the newly discovered adiabatic evolution approach. We acknowledge the main problem in adiabatic quantum computation to be the lack of insight that common programmers have about the design of Hamiltonians. In the present work we provide necessary background in physics and algebra and the basics of adiabatic quantum computation with comprehensive discussion of both examples seen in literature and new ones. We examine some flow control constructs like loops and branching from the adiabatic quantum perspective to illustrate the main design problems as a first step towards the development of an adiabatic quantum programming infrastructure.
Qualitative system identification
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 1992., 1992.) Say, Ahmet Celal Cem.; Kuru, Selahattin,
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 under consideration, 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 thig reasoning task, which is promising for diagnosis applications, are discussed.
Real-time vector automata
(Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2013., 2013.) Salehi, Özlem.; Say, Ahmet Celal Cem.
Finite automaton has been one of the most studied models in automata theory. The limited power of the standard model has led researchers to make various extensions to the standard model. Counter automaton, automaton with multiplication, nite automaton over groups are some of the examples of such extensions. In this thesis, we study the computational power of real-time nite automaton that has been augmented with a vector of dimension k, and programmed to multiply this vector at each step by an appropriately selected k k matrix. Only one entry of the vector can be tested for equality to 1 at any time. We study the classes of languages recognized by deterministic, nondeterministic, and "blind" versions of these machines and compare them with each other. It turns out that these machines are closely related to some of the classical models like counter automata and generalized nite automata.
Source separation via weakly-supervised and unsupervised deep learning
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2023., 2023) Karamatlı, Ertuğ.; Say, Ahmet Celal Cem.; Kırbız, Serap.
Source separation has been a key research area over the past several decades, and the emergence of deep learning approaches has revolutionized the field. Although supervised methods have been the pillars of this revolution, training such models often requires synthetic mixture datasets that may not represent real-world mixture signals adequately. In this thesis, we focus on single-channel source separation methods that are trained without having access to the underlying isolated source signals. This enables the training of source separation models solely on real-world mixture recordings that do not have corresponding source signals at hand. Therefore, it enables the models to be trained on a large amount of unlabeled or weakly- labeled data without additional labeling effort. We approach this problem in several different ways. First, we start with developing a decomposition-based weakly-supervised model that utilizes the class labels of the sources that are present in mixtures. We apply this weak class supervision approach to superimposed handwritten digit images using both non-negative matrix factorization (NMF) and generative adversarial networks (GANs). Second, we introduce another decomposition- based model that employs variational autoencoders (VAEs) to apply our weak class supervision approach to audio signals. Third, we introduce two purely unsupervised methods, which are trained exclusively on the mixture signals in a self-supervised fashion. The results of our experiments demonstrate that the proposed weakly-supervised and unsupervised methods are viable and mostly on par with the fully supervised baselines. We conclude that it is possible to replace supervised training with weakly-supervised and unsupervised methods in compatible real-world applications for better results.
Stochastic diffusion search and voting methods
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2006., 2006.) Nircan, Ahmet Kutsi.; Atılgan, Ali Rana.; Say, Ahmet Celal Cem.
This study compares known social choice rules in the context of agent based search and introduces two new variants of stochastic diffusion search algorithm. Performance comparison to match a correct ordering of 36 voting algorithms that are derived from 23 known social choice rules are made. A simple text search framework is used for the simulation where agents are given parts of a search key. Individual preferences of agents are then fed to 36 different voting algorithms. Results are compared against the known correct ordering and correct top choices. A similarity coefficient and a top choice match coefficient is used to compare the performances of the voting algorithms. Simulations are made for each length of search key part and each length of search space. A population based search algorithm, stochastic diffusion search (SDS), is improved to include different voting methods. A shared memory and an individual memory variant are developed and performances compared against original SDS. Tests are made with text and image search frameworks. The similarity and top choice match coefficients are used for the text search framework. Image test performances are measured by calculating distance of the found location to the known correct location of the image. It is found that the new algorithms developed in this study considerably outperforms the original SDS algorithm.
Succinctness analysis of finite automaton models
(Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2017., 2017.) Erdoğan, Emre.; Say, Ahmet Celal Cem.
Finite state automaton, or ﬁnite automaton, is a mathematical model of compu tation and has been one of the most studied models in automata theory. Throughout the years, many diﬀerent types of ﬁnite state automata are proposed, such as deter ministic, 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 ﬁnite automata. First, we thoroughly study the topic of simulating various ﬁnite automata by deter ministic ﬁnite automata. Second, we work with three diﬀerent 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 eﬃciently describe regu lar languages over unary alphabets and we introduce algorithms to show the eﬃcient realization of closure properties of UFPF.

Browsing by Author "Say, Ahmet Celal Cem."

Results Per Page

Sort Options