Dissertation Defense

The dramatic increase of companies and consumers that heavily depend on networks mandates the creation of reliable network devices. Such reliability can be achieved by testing both the conformance of individual protocols of an implementation to their corresponding specifications and the interaction between different protocols. With the increase of computer power and the advances in network testing research, one would expect that efficient approaches for testing network implementations would be available. However, this question is still far from answered due to reasons such as the complexity of networks protocols, the need for different protocols to interoperate, the limited information on implementation because of proprietary codes, and the potentially unbounded size of the network to be tested.
To address these issues, a novel technique is proposed that improves the quality of the test while reducing the time and effort network testing requires. The proposed approach achieves these goals, by automating the process of creating models to be used for validating an implementation. More precisely, it utilizes observations acquired by monitoring the behavior of the implementation for the automatic generation of models. In this way, generated models can accurately represent the actual implementation. Thus, testing is reduced to the problem of verifying that certain properties hold on the generated model. This work presents algorithms that efficiently create models from observations and shows their effectiveness through the presentation of three different examples.
In addition, the difficulty of validating models using theorem provers is addressed. To address this issue, techniques available in the literature are utilized and approaches that assist testers with completing proofs are proposed. Results suggest that the complexity of making proofs using theorem proving can be reduced when models are members of the same class, i.e. their structure can be predicted.
A final problem this work addresses is that of scale, i.e. the impracticability or even impossibility of testing every possible network configuration. To address this problem, the concept of "self-similarity" is introduced. A self-similar network has the property that can be sufficiently represented by a smaller network. Thus, proving the correctness of a smaller network is sufficient for proving the correctness of any self-similar network that can be represented by this smaller one.

This thesis is a contribution to solving problems of extracting optimal controls for complex systems. Its novelty consists of a detailed examination of Finsler geometry based control by connections as proposed by Kohn and Nerode and its relation to Pontryagin's maximum principle. The long term hope is that these methods will form the underpinning of the applications of control of hybrid systems. Any advances in mathematical and algorithmic techniques for solving such problems would have wide application in business, industry, and science. The widespread use of Bellman's dynamic programming, Dantzig's linear programming, Kalman's optimization with linear quadratic cost functions, demonstrate this. But symbolic and numerical techniques historically have fallen well short of yielding efficient computation procedures to obtain near optimal controls for complex systems. Most investigations have been based on Pontryagin's geometric representation of optimal control and his maximum principle. Kohn and Nerode have proposed a different problem formulation aimed at extracting robust controls as a function of state (synthesis problem with a robustness requirement) in the context of a Finsler geometry corresponding to the optimal control problem. This leads to the study of geometric, symbolic, and numerical methods for solving geodesic equations for connections in Finsler Geometry. A principal result of this thesis is the determination of the relations between the Finsler and Pontryagin formulations of optimal control, and the transformation from one to the other. A second principal result is establishing the relations between robustness and curvature. Curvature is used to quantify the spread of geodesics due to disturbances. Finally, the thesis concludes with numerical integration schemes for computing controls and local connections.

The general problem that we consider is the real-time enhancement of a noisy image as it arrives column by column (time is associated with the horizontal axis). The enhancement is modeled by a column of real values between 0 and 1 (with as many pixels as in the noisy image column), which is used as a mask on the noisy image column. That is, the clean image column is estimated by multiplying the noisy image column by the mask column, pixel by pixel. In this work, the real-valued column is attained by "fuzzifying" a binary column, which is estimated from the noisy image column using a prior model and a noise model. The prior model is specified by a statistical distribution that assigns to binary columns a probability of occurrence. The noise model is specified by a statistical distribution that assigns the likelihood of occurrence of the noisy image column given the binary column. These statistics should either be known or estimated from a training set of typical images from the application area. Given models of this type, our task is to design an algorithm that will produce the sought-after binary and "fuzzified" columns in "real-time," that is as the noisy image arrives column by column. In many applications signals are transformed into images by taking the squared norm of the Short-Time Fourier Transform of the signal, called the spectrogram. These spectrograms are extremely redundant; columns represent spectral information of overlapping time intervals. We, therefore, tested the possible applicability of image processing algorithms to the problem of increasing intelligibility in the hearing aid application. It was our hypothesis that for every spectrogram image of noisy speech there exist a binary image and its "fuzzified" image that (along with the noisy spectrogram image) contain the information essential for estimating the clean speech signal. The proposed processing was tested on 24 normal hearing subjects using the Modified Rhyme Test. Unfortunately, the specific choices that we made in the development of our processing methodology decreased the intelligibility of noisy speech signals.

In this work we discuss two problems that appear in modern radar waveform design. First, we propose a new approach to one of the most challenging problems in this area of research - the construction of waveforms with optimal ambiguity characteristics in a chosen a priori region surrounding the main lobe. Our approach is based on the projection of the signal onto an appropriate orthonormal basis in the space of radar waveforms and approximating the signal with desired ambiguity properties by a finite number of basis waveforms. In particular, we consider well-known Hermite waveforms as the basis functions and discuss the problem of minimizing the volume under the ambiguity surface over a certain given region. The second part of the dissertation is devoted to the problem of the range sidelobe suppression in stepped-frequency LFM pulse trains. Frequency stepping is one of the known techniques employed by modern radars to achieve high range resolution. The main advantage of this approach is that the instantaneous bandwidth of a radar is quite small compared with the total processing bandwidth. This allows the transmission of waveforms with extremely wide overall bandwidth (and, as a consequence, the attainment of high range resolution) without the usage of the expensive hardware needed to support the wide instantaneous bandwidth. We present a systematic approach for designing pulse trains producing the autocorrelation function whose sidelobes are less than some predetermined level.

In this dissertation, we propose a nested bitemporal relational data model, using nested relations, and we also develop algebra and calculus languages for this model. The fundamental construct for representing temporal data is a bitemporal atom that consists of five parts: a value, its validity period, and the time this data is recorded in the database. Bitemporal data is attached to attributes, and arbitrary levels of nesting are allowed. The algebra includes operations to manipulate bitemporal data, to restructure nested bitemporal relations, and to rollback database to a designated state in the past. We have also defined the concept of ‘context’ for using bitemporal data: bitemporal context, historical context, and current context. BtSQL, a preprocessor for the bitemporal SOL language, query syntax allows end users to incorporate bitemporal, current and historical context. We defined and implemented BtSQL for the specification of bitemporal queries in different context. It translates a bitemporal query specification to a standard SQL statement. BtSQL includes select, insert, delete, and update statements of SQL extended for bitemporal relational databases. A prototype implementation has been completed in an object-relational database system to demonstrate the feasibility of the model defined in this thesis.

Programming has evolved through a number of different paradigms, including the Object Oriented Paradigm, which aims to make programming more efficient and better understood. Despite various enhancements in programming languages, environments, and pedagocial approaches, novices are still faced with many challenges when learning to program. Computer science departments in universities world wide are in a crisis of high drop out and failure rates, as well as low enrollment in computr science courses. It has been shown that experienced programmers utilize plan representations to encode programming concepts and tasks. Studies of novice programmers reveal that most major errors are a result of plan and object management. Students exhibit difficulties conceptualizing and implementing objects. Objects, while representing the real world, can be intangible, vague, and lack context for novice programmers. A Plan-Object learning paradigm that reinforces concepts of object design through plan representation can aid students' ability to design and implement objects, as well as their ability to utilize objects into problem solving. Our approach also contributes to the Objects-First vs. Objects-Next debate by introducing objects using plans. To address the problems faced by novice programmers, an interactive learning environment, Web Plan Object Language (WPOL), is designed. WPOL is plan oriented and teaches novices programming by plan observation, integration, and creation. In WPOL, an object or a function can be simply understood by their defined plans (context). This study empirically examines two groups of novice programmers; one learning programming with objects by using traditional methods and another with exposure to the Plan-Oriented learning paradigm and WPOL. The results demonstrate the positive impact of WPOL on novice's comprehension of object design and incorporation of objects into their programs.

Justification Logic is the study of a family of logics used to reason about justified true belief. Dynamic Epistemic Logic is the study of logics used to reason about communication and true belief. This dissertation is a first step in merging these two areas, in that it defines theories for a joint language in which we may reason about communication alongside justified true belief. After some preliminary matters, we go through a comprehensive survey of Dynamic Epistemic Logic, which primes us for the work at the end of the text. We then move into the core work of the dissertation, where we introduce a number of extensions of existing languages and theories of Justification Logic. Our extensions are all based on the work of Sergei Artemov, who extended the language of propositional logic by the addition of formula-labeling terms. The terms have a derivation-compatible structure that allows us to view terms as evidence verifying the truth of the formulas they label, which provides us with a means for reasoning about justified true belief.
We look at extensions of these theories that allow us to reason about evidence admissibility, by which we mean that the evidence may be taken into account when considering the truth of a formula, though the evidence need not be conclusive. A further extension adds a unary modal operator that we use to reason about alternative evidence possibilities.
Nominaled extensions of the latter languages allow us to express a notion of dynamic evidence introduction, whereby we may introduce a term t as admissible as evidence for F. These extensions lead us to the final chapter of the text, where we combine our various systems of Justification Logic with the framework of Dynamic Epistemic Logic. Such joint theories contribute to the ongoing work aiming to provide a better foundational account of the reasoning of computational social agents.

Problem solvers have at their disposal many heuristics that may support effective search. The efficacy of these heuristics, however, varies with the problem class. This research is on machine-learning techniques to select appropriately from among a large body of heuristics, and combine them into a weighted mixture that works well on a specific class of constraint satisfaction problems. The learning used here is a form of self-supervised reinforcement learning. The training instances come from the solver's own (likely imperfect) successful searches. As a result, learning lacks reliable information on how much any individual decision or mutual interaction of heuristics influenced overall search performance. A pre-existing learner has weights for heuristics learned from the size of the search space explored. The new algorithms proposed and tested here use different ways to gauge and adapt search performance; they learn from the accuracy, intensity, frequency and distribution of heuristics' preferences. Stochastic methods address challenges for that learner on hard problems under limited resources and with large and contradictory set of heuristics. This work is an important step toward automated problem solving. The resultant solver is effective, robust and self-adaptive. It thereby relieves the user of the burden of providing domain specific knowledge for a solver. Although the experimental work is done on constraint satisfaction problems, the machine learning techniques presented here are general, and therefore applicable to many other domains.

Previous research has proposed that any model of language learning should use the Subset Principle to guide hypothesis selection when the language domain contains at least two languages such that one is a subset of the other (Gold, 1967; Berwick, 1985; Manzini & Wexler, 1987; Wexler & Manzini, 1987). Informally, the Subset Principle states that the learner should select a language that is: a) compatible with the input data, and, b) does not properly contain any other language that is compatible with the input data. We will investigate, from both an empirical and theoretical perspective, psychocomputational models of language learning that abide by the Subset Principle. We intend “psychocomputational models” to include computational models that are in line with research in psycholinguistics, developmental psychology and linguistics (Sakas, 2004). Empirical research will focus on the creation and analysis of simulated language learners equipped with memory for past grammars. A comparison study will also be done between traditional total ordering learners and our partial ordering learners. Theoretical research will be concerned with investigating how the shape of the language domain, in terms of both cross-language ambiguity and the partial ordering of subset-superset relationships, would affect learner performance. Although there has been some computational research that attempts to address the problems that are introduced when learning in domains that contain superset languages, our research will make its contributions by directly modeling the Subset Principle within a psychologically compelling framework.

Robot programming is a quintessential hands-on computing activity, and this rightfully accounts for much of its growing popularity in the CS curriculum. However, as robot programming moves from an elective curiosity into the mainstream of the curriculum, this hands-on character will create logistical challenges of lab availability to students. Remote access to the lab during off-hours can ameliorate this problem. This research is concerned with the design, development, and implementation of a "Networked Robotics Laboratory" that will allow anyone on the Internet to learn a robot programming language, and use that language to control a robot from a distance. The project combines Inter-Networking, Multimedia, and Distance Learning Conceptualizations into a comprehensive system that broadens the availability and effectiveness of robot programming instruction. Typical robotics labs are limited by the requirement of physical access, the need for the presence of instructional and supervisory personnel, and delays resulting from the learning curve of visiting students. An important outcome of this work has been the removal of the first two requirements (physical access and the presence of personnel) and a significant reduction of the learning curve. The efficacy of learning a robot programming language via the Web was also confirmed in experiments across several academic group levels. Most importantly, the networked robotics lab has proven to be a powerful way to motivate learning.