Recently, interest in the Graphics Processing Unit (GPU) for general purpose parallel applications development and research has grown. Much of the current research on the GPU focuses on the acceleration of regular problems, as irregular problems typically do not provide the same level of performance on the hardware. We explore the potential of the GPU by investigating four problems on the GPU with regular and/or irregular properties: lookback option pricing (regular), single-source shortest path (irregular), maximum flow (irregular), and the task matching problem using multi-swarm particle swarm optimization (regular with elements of irregularity). We investigate the design, implementation, optimization, and performance of these algorithms on the GPU, and compare the results. Our results show that the regular problem achieves greater performance and requires less development effort than the irregular problems. However, we find the GPU to still be capable of providing high levels of acceleration for irregular problems.

Regular path queries (RPQ’s) are given by means of regular expressions and ask for matching patterns on labeled graphs. RPQ’s have recently received great attention in the context of semistructured data, which are data whose structure is irregular, partially known, or subject to frequent changes. One of the most important problems in databases today is the integration of semistructured data from multiple sources modeled as views. In this setting, the database is not available, and given a user query, the system has to answer based solely on the information provided by the views. The problem is computationally hard, and the well-known algorithm for solving it runs in 2EXPTIME. In this paper, we provide practical evidence that this algorithm performs poorly on the average as well. Then, we propose automata- theoretic techniques which make the view-based answering of RPQ’s more feasible in practice.

Regular path queries are the building block of almost any mechanism for querying semistructured data. Despite the fact that the main applications of such data are distributed, there are only few works dealing with distributed evaluation of regular path queries. In this thesis we present a message-efficient and truly distributed algorithm for computing the answer to regular path queries in a multi-source semistructured database setting. Our algorithm has several desirable properties. First, it is general as it works for the larger class of weighted regular path queries on weighted semistructured databases. Second, it performs a progressive evaluation, that is, partial answers can be represented to the user as soon as they are computed while she is waiting for new answers to arrive. Third, the proposed algorithm is symmetric among processes, i.e., they all run the same algorithm. And finally, it does not need a separate termination detection algorithm as it can detect the global termination simply by using an spanning tree.

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We study the syntactic complexity of suffix-, bifix-, and factor-free regular languages, star-free languages including three subclasses, and R- and J-trivial regular languages. We found upper bounds on the syntactic complexities of these classes of languages. For R- and J-trivial regular languages, the upper bounds are n! and ⌊e(n-1)!⌋, respectively, and they are tight for n >= 1. Let C^n_k be the binomial coefficient ``n choose k''. For monotonic languages, the tight upper bound is C^{2n-1}_n. We also found tight upper bounds for partially monotonic and nearly monotonic languages. For the other classes of languages, we found tight upper bounds for languages with small state complexities, and we exhibited languages with maximal known syntactic complexities. We conjecture these lower bounds to be tight upper bounds for these languages. We also observed that, for some subclasses C of regular languages, the upper bound on state complexity of the reversal operation on languages in C can be met by languages in C with maximal syntactic complexity. For R- and J-trivial regular languages, we also determined tight upper bounds on the state complexity of the reversal operation.

In estimating auditory Evoked Potentials (EPs) from ongoing EEG the number of sweeps should be reduced to decrease the experimental time and to increase the reliability of diagnosis. The &macr / rst goal of this study is to demon- strate the use of basic estimation techniques in extracting auditory EPs (AEPs) from small number of sweeps relative to ensemble averaging (EA). For this purpose, three groups of basic estimation techniques are compared to the traditional EA with respect to the signal-to-noise ratio(SNR) improve- ments in extracting the template AEP. Group A includes the combinations of the Subspace Method (SM) with the Wiener Filtering (WF) approaches (the conventional WF and coherence weighted WF (CWWF). Group B con- sists of standard adaptive algorithms (Least Mean Square (LMS), Recursive Least Square (RLS), and one-step Kalman &macr / ltering (KF). The regularization techniques (the Standard Tikhonov Regularization (STR) and the Subspace Regularization (SR) methods) forms Group C. All methods are tested in sim- ulations and pseudo-simulations which are performed with white noise and EEG measurements, respectively. The same methods are also tested with experimental AEPs. Comparisons based on the output signal-to-noise ratio (SNR) show that: 1) the KF and STR methods are the best methods among the algorithms tested in this study,2) the SM can reduce the large amount of the background EEG noise from the raw data, 3) the LMS and WF algo- rithms show poor performance compared to EA. The SM should be used as 1 a pre-&macr / lter to increase their performance. 4) the CWWF works better than the WF when it is combined with the SM, 5) the STR method is better than the SR method. It is observed that, most of the basic estimation techniques show de&macr / nitely better performance compared to EA in extracting the EPs. The KF or the STR e&reg / ectively reduce the experimental time (to one-fourth of that required by EA). The SM is a useful pre-&macr / lter to signi&macr / cantly reduce the noise on the raw data. The KF and STR are shown to be computationally inexpensive tools to extract the template AEPs and should be used instead of EA. They provide a clear template AEP for various analysis methods. To reduce the noise level on single sweeps, the SM can be used as a pre-&macr / lter before various single sweep analysis methods. The second goal of this study is to to present a new approach to extract single sweep AEPs without using a template signal. The SM and a modi- &macr / ed scale-space &macr / lter (MSSF) are applied consecutively. The SM is applied to raw data to increase the SNR. The less-noisy sweeps are then individu- ally &macr / ltered with the MSSF. This new approach is assessed in both pseudo- simulations and experimental studies. The MSSF is also applied to actual auditory brainstem response (ABR) data to obtain a clear ABR from a rel- atively small number of sweeps. The wavelet transform coe&plusmn / cients (WTCs) corresponding to the signal and noise become distinguishable after the SM. The MSSF is an e&reg / ective &macr / lter in selecting the WTCs of the noise. The esti- mated single sweep EPs highly resemble the grand average EP although less number of sweeps are evaluated. Small amplitude variations are observed among the estimations. The MSSF applied to EA of 50 sweeps yields an ABR that best &macr / ts to the grand average of 250 sweeps. We concluded that the combination of SM and MSSF is an e&plusmn / cient tool to obtain clear single sweep AEPs. The MSSF reduces the recording time to one-&macr / fth of that re- quired by EA in template ABR estimation. The proposed approach does not use a template signal (which is generally obtained using the average of small number of sweeps). It provides unprecedented results that support the basic assumptions in the additive signal model.

Thesis (D. Min.)--Westminster Theological Seminary, Philadelphia, 1988. / Includes bibliographical references (leaf [77]).

Αντικείμενο της παρούσας εργασίας αποτέλεσε ο σχεδιασμός του γλωσσικού μαθήματος για τους μη φυσικούς ομιλητές της ελληνικής γλώσσας που φοιτούν στο δημοτικό σχολείο με βάση τον αντίστοιχο σχεδιασμό του γλωσσικού μαθήματος που εκπονήθηκε στο πλαίσιο του Προγράμματος Εκπαίδευσης Μουσουλμανοπαίδων. Αρχικά εντοπίστηκαν και καταγράφηκαν οι κειμενικοί και γραμματικοί στόχοι των σχολικών εγχειριδίων της Γ και Δ τάξης του δημοτικού σχολείου που εκπονήθηκαν στο πλαίσιο του Π.Ε.Μ. Στη συνέχεια έγινε εφαρμογή αυτού του γλωσσικού σχεδιασμού στα σχολικά εγχειρίδια της Γ και Δ τάξης που διδάσκονται σε όλα τα δημοτικά σχολεία της ελληνικής επικράτειας. Η έρευνα εντάσσεται στο πλαίσιο του ευρύτερου επιστημονικού ενδιαφέροντος για τη διδασκαλία της ελληνικής γλώσσας ως ξένης. Πρωταρχικός της στόχος ήταν να αναζητήσει σε ποιο βαθμό ο σχεδιασμός του γλωσσικού μαθήματος μέσα από τα σχολικά εγχειρίδια του Π.Ι. είναι κατάλληλος και για τους αλλόγλωσσους μαθητές του ελληνικού σχολείου. Βασικό κριτήριο για αυτή την εφαρμογή υπήρξε ο γλωσσικός σχεδιασμός του Π.Ε.Μ. Συγκεκριμένα ερευνήθηκαν οι κειμενικοί και οι γραμματικοί στόχοι (φωνολογία, μορφολογία, σύνταξη) των σχολικών εγχειριδίων της Γ και Δ τάξης του δημοτικού σχολείου. Η ανάλυση της έρευνας έδειξε πως ένα μεγάλο μέρος των κειμενικών και γραμματικών στόχων των σχολικών εγχειριδίων είναι πολύ απαιτητικοί για τους αλλόγλωσσους μαθητές αυτών των τάξεων. Μερικοί από αυτούς τους στόχους μπορούν ενδεχομένως να εφαρμοστούν μερικώς και άλλοι υπό κάποιες προϋποθέσεις. Η ύπαρξη του ενός και μοναδικού σχολικού εγχειριδίου στο ελληνικό σχολείο, διαμορφωμένου μάλιστα με βάση ένα σχεδιασμό για μαθητές φυσικούς ομιλητές της ελληνικής γλώσσας, αποτελεί ένα από τα μεγαλύτερα εμπόδια για την υιοθέτηση και εφαρμογή προσαρμοσμένου με τις εκάστοτε ανάγκες διδακτικού υλικού. Η υιοθέτηση του πολλαπλού-εναλλακτικού βιβλίου που θα καλύπτει τις ιδιαίτερες ανάγκες των μαθητών και θα επιτρέπει την αυτενέργεια των εκπαιδευτικών θεωρείται απαραίτητη. / -

XML documents and related technologies represent one of the most widespread ways how data on the Web are maintained and interchanged. Unfortunately, many of the real-world documents contain various types of consistency issues that prevent their successful automated processing. In this thesis we focus on the problem of the structural invalidity and its correction. In particular, having one potentially invalid XML document modeled as a tree, and a schema in DTD or XML Schema languages modeled as a regular tree grammar, our goal is to find all the minimal corrections of this tree. The model we proposed builds on top of the recursively nested structures of correction multigraphs, where the shortest paths are being found. For this purpose we formally introduce three correction strategies with different pruning optimizations applied. According to the experiments we performed, the refinement correction strategy not only significantly outperforms all the other existing approaches, but also guarantees important characteristics the others cannot. Powered by TCPDF (www.tcpdf.org)

AN ABSTRACT OF THE DISSERTATION OF Linda Elaine Buerck, for the Doctor of Philosophy degree in Curriculum and Instruction, presented on November 12, 2009, at Southern Illinois University Carbondale. TITLE: EFFECTS OF ENROLLMENT IN CO-TEACHING CLASSES ON THE ACADEMIC PERFORMANCE OF HIGH SCHOOL STUDENTS WITHOUT DISABILITIES MAJOR PROFESSOR: D. John McIntyre, Professor of Curriculum and Instruction, Ed.D., University of Syracuse This study examined the impact of enrollment in co-teaching classes on the grades earned by high school students without disabilities. The study also included analyses of teacher responses to a survey regarding their experience with the co-teaching model at the school. The study sought to examine (1) the extent to which enrollment in co-teaching classes affects academic achievement of regular education students; (2) the attributes of co-teaching classrooms that may have an effect on the academic performance of all students; and (3) the similarities and differences in opinion of regular education teachers and special education teachers regarding the co-teaching model. Student grades were analyzed using descriptive statistical procedures. Thirty-eight classes were eligible for the study. A total of 719 semester grades were recorded, representing 441 students. Two hundred thirteen of the students were enrolled in more than one of the classes in the study concurrently. A subset of data was produced using only the grades earned by the 124 students who were enrolled in at least one regular education class and at least one co-teaching class in the same semester. The dependent variable was course grades. The primary independent variable was the type of class--regular education or co-teaching. Other independent variables included course content (Communication Arts, Mathematics, Science or Social Studies), grade in school (9th, 10th, 11th, or 12th), and achievement level. Student achievement levels were classified as low (0.00-4.99), average (5.0-7.99), or high (8.0-11.0) based on overall grade point averages. Paired samples t-tests demonstrated significant difference between grades earned in co-teaching classes and grades earned in regular classes. Student grades in all three achievement levels were higher in co-teaching classes than in regular education classes. A Cohen's d coefficient was generated to determine the effect size of the differences between teaching models. A medium effect size was detected for grades earned in co-teaching classes for students in the high and average achievement levels. There was a large effect size for grades earned in co-teaching classes for students in the low achievement category. Teacher responses to a survey constructed solely for use in this study were analyzed using inductive analysis. Ten regular education teachers and seven special educators responded to the survey (response rate of 77% for all teachers.) The three themes that emerged from all teachers were the need for common planning time, the need for quality professional development and training activities, and the need to clearly define the roles of each co-teacher in the pair. Responses to selected questions were also analyzed by directly comparing the responses given by the 13 pairs of teachers who were assigned to the same co-teaching class. There were significant differences in perceived roles between the pairs of teachers.

L’analyse d’accessibilité est une des composantes de l’analyse de modèles. Elle consiste à modéliser un système complexe par trois ensembles : le langage initial, le langage des configurations indésirables et un système de réécriture. Le langage initial et le langage des configurations indésirables sont des ensembles de termes. Un terme est un mot mais construit à partir de symboles d’arités supérieures à 1. Le système de réécriture représente la dynamique du système complexe. C’est un ensemble de règles qui permettent d’obtenir un nouveau terme à partir d’un terme original. Pour effectuer une analyse d’accessibilité à partir de cette modélisation, on peut calculer l’ensemble des configurations accessibles. Cet ensemble aussi appelé ensemble des descendants est obtenu en appliquant le système de réécriture sur le langage initial jusqu’à ne plus obtenir de nouveaux termes. Une fois l’ensemble des descendants calculé, il reste à faire l’intersection entre celui-ci et l’ensemble des configurations indésirables. Si cette intersection est vide, alors il n’y a pas de configuration indésirable accessible, sinon les configurations présentes dans cette intersection sont accessibles. Cependant, l’ensemble des descendants n’est pas calculable dans le cas général. Pour contourner ce problème, nous calculons une sur-approximation des descendants. Ainsi, si l’intersection est vide, cela signifie toujours qu’aucune configuration indésirable n’est accessible. A contrario, s’il existe un terme dans l’intersection, il n’est pas possible de déterminer s’il s’agit d’un faux positif ou d’une configuration indésirable accessible. La précision de la sur-approximation est alors déterminante. / Reachability analysis is part of model checking. It consists to model complex systems by three sets : initial language, unwanted configurations and rewrite system. The initial language and the unwanted configurations language are sets of terms. Terms are words which are construct with symbols that have an arity that can be greater than 1. The rewrite system represent the dynamic of the complex system. It is a set of rules that permit from a initial term to obtain a new term. One of the approaches to analyze reachability from this modelling is to compute the set of reachable configurations. This set which is called set of descendants is obtained by applying the rewrite system on the initial language until obtaining no more new terms. After the set of descendants is computed, we need to compute the intersection between this set and the unwanted configurations set. If this intersection is empty then there is no unwanted configuration reachable, else the configurations in this intersection are reachable. However, the set of descendants is not computable in the general case. To bypass this problem, we compute an over-approximation of descendants.Now, if the intersection is empty, we keep proving that no unwanted configuration is reachable. Nevertheless, if the intersection is not empty, it is not possible to know if it comes from false-positives or form unwanted reachable configurations. So, the precision of the over-approximation is decisive.