Today, as computer systems are ubiquitous in our everyday life, there is no need to argue that their correctness is of capital importance. In order to prove (in a mathematical sense) that a given system satisfies a given property, formal methods have been introduced. They include concepts such as model checking and synthesis. Roughly speaking, when considering synthesis, we aim at building a model of the system which is correct by construction. In order to do so, models are mainly borrowed from game theory. During the last decades, there has been a shift from two-player qualitative zero-sum games (used to model antagonistic interactions between a system and its environment) to multiplayer quantitative games (used to model complex systems composed of several agents whose objectives are not necessarily antagonistic). In the latter setting, the solution concepts of interest include numerous equilibria, such as Nash equilibrium (NE) and subgame perfect equilibrium (SPE). While the existence of equilibria is widely studied, it is also well known that several equilibria may coexist in the same game. Nevertheless, some equilibria are more relevant than others. For example, if we consider a game in which each player aims at satisfying a given qualitative objective, it is possible to have both an equilibrium in which no player satisfies his objective and another one in which each player satisfies it. In this case one prefers the latter equilibrium which is more relevant.In this thesis, we focus on multiplayer turn-based games played on graphs either with qualitative or quantitative objectives. Our contributions are twofold: (i) we provide equilibria characterizations and (ii) we use these characterizations to solve decision problems related to the existence of relevant equilibria; and characterize their complexities. Firstly, we provide a characterization of a weaker notion of SPE (weak SPE) in multiplayer games with omega-regular objectives based on the payoff profiles which are realizable by a weak SPE. We then adopt another point of view by characterizing the outcomes of equilibria instead of their payoff profiles. In particular we focus on weak SPE outcome characterization. As for some kinds of games (e.g. multiplayer quantitative Reachability games), weak SPEs and SPEs are equivalent, this characterization is useful in order to study SPEs in these games.Secondly, we use those different equilibrium characterizations to provide the exact complexity classes of different decision problems related to the existence of relevant equilibria. We mainly focus on the constrained existence problem: if each player aims at maximizing his gain, this problem asks whether there exists an equilibrium such that each resulting player’s gain is greater than a threshold (one per player). We also consider variants of relevant equilibria based on the social welfare and the Pareto optimality of the players’ payoff. In this way, we prove the exact complexity classes for (i) the weak SPE constrained existence problem in multiplayer games with classical qualitative objectives such as Büchi, co-Büchi and Safety and (ii) the NE and SPE constrained existence problems (and variants) for qualitative and quantitative reachability games. In the latter case, the upper bounds on the required memory for such relevant equilibria are studied and proved to be finite. Studying memory requirements of strategies is important since with the synthesis process those strategies have to be implemented.Finally, we consider multiplayer, non zero-sum, turn-based timed games with qualitative Reachability objectives together with the concept of SPE. We prove that the SPE constrained existence problem is EXPTIME-complete for qualitative Reachability timed games. In order to obtain an EXPTIME algorithm, we proceed in different steps. In the first step, we prove that the game variant of the classical region graph is a good abstraction for the SPE constrained existence problem. In fact, we identify conditions on bisimulations under which the study of SPE in a given game can be reduced to the study of its quotient. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

[pt] Este estudo investiga os comportamentos de processamento de um grupo de Brasileiros bilíngues instrucionados de português L1 e inglês L2, (n igual a 21), e um grupo de monolíngues de inglês norte-americano (n igual a 11) durante a sua compreensão de sentenças no present perfect (vs. simple past) em uma tarefa on-line de leitura auto-monitorada (Self-Paced Reading - SPR). Uma medida off-line, Tarefa de Julgamento de Aceitabilidade (Acceptability Judgment Task - AJT) foi utilizado como uma linha de base de conhcimento explícito da estrutura. Os resultados são comparados, qualitativamente, entre o grupo do monolíngue e bilíngue para investigar a sensibilidade, de cada grupo, às manipulações experimentais em tempo/aspecto, correspondência adverbial, e telicidade. O present perfect foi usado para os estímulos, pois é um tempo verbal do inglês adquirido mais tardiamente o que permite estudar as estratégias de processamento de bilíngues de nível mais avançado. Ambos os grupos foram capazes de reconhecer incongruências na atividade off-line. No entanto, o grupo monolíngue não foi sensível à condição de incongruência adverbial em tempo real, na atividade SPR. Por outro lado, o grupo bilíngue mostrou-se mais sensível a variável da incongruência adverbial, apresentando um comportamento que indica uma facilitação (automatização) de processamento da condição. O grupo monolíngue mostrou sensibilidade significativo às manipulações de telicidade em várias regiões do sintagma verbal. Diferenças entre os dois grupos foram observadas nas suas distribuições de tempos de leitura entre as condições em várias regiões da frase e elas são discutidas em termos de estratégias de processamento. Os monolíngues apresentaram efeitos de processamento integrativo no final da frase, os quais não são observados no grupo bilíngue. Atualmente, não há estudos com condições experimentais semelhantes que investiguem como os brasileiros bilíngues, avançados em inglês comportam na compreensão on-line de sentenças em inglês no present perfect. / [en] This study investigates the processing behaviors of a group of Brazilian bilingual students, instructed, advanced English students (n equal 21), and an English monolingual control group (n equal 11) during their comprehension of Present Perfect and Simple Past sentences in an on-line, self-paced reading (SPR) task. An off-line Acceptability Judgment Task (AJT) provides a baseline measure of explicit knowledge in order to validate the on-line results. The results are compared, qualitatively, between the bilingual and monolingual groups in order to investigate their sensitivity to experimental manipulations in Tense/Aspect, adverbial (Mis)match, and Telicity. The Present Perfect was used for the stimuli as it is a late-acquired feature of English which allows for the study of processing strategy of advanced level students. While both groups were able to recognize Mismatches off-line, monolinguals were not sensitive to the Mismatch condition in the on-line experiment. Surprisingly, the bilingual group showed more sensitivity to the adverbial Match variable, showing a processing facilitation in the Match condition as well as some mismatch sensitivity as well. The monolingual group showed significant effects for Telicity at multiple sentence regions. Some qualitative differences were seen between the two groups in their reading-time contours across the verb phrase. The monolinguals show within-group consistency across multiple conditions and signs of integrative processing (wrap-up) effects in their processing patterns which are not seen among the bilingual group. There are currently no studies with similar experimental conditions which investigate the on-line comprehension of the English Present Perfect with Brazilian Portuguese-English bilinguals in comparison to American English monolinguals.

Made available in DSpace on 2016-04-28T18:23:43Z (GMT). No. of bitstreams: 1 Celso Frade.pdf: 1002866 bytes, checksum: 3aae61084839d164917eabb55ae16230 (MD5) Previous issue date: 2008-05-12 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The present perfect (PrP) is a complex issue for researchers and non-native speakers of English that has been studied from many different perspectives. This research aims at showing a description of the PrP in the language of news media and brings to light new insights into the teaching of English as a foreign language. Linguistic research on the nature of news stories has seen a great increase since the 1970s. So, the theoretical underpinning for the research provides a briefing of the state-of-the-art literature on the area that includes views on tense and aspect, Travaglia (1985) and Comrie (1985), the usage of PrP according to Schwenter (1994), Michaelis (1998), Engel & Ritz (2005)) and Nishiyama & Koenig (2005, 2006) and the meaning of discourse by Bell (1991), Fowler (1991), Halliday (1978, 1985) and Fairclough (1995, 1999). It, therefore, provides a clear picture of what has been researched on the uses of the PrP and its various functions in the language of news media. More specifically, the research reported here, which used the documentary research methodology (Sanghera:2002), uses examples from the data collected, which include 60 sample articles from the websites of quality British and American broadsheets, such as The Guardian and The Independent (UK), The New York Times and The USA Today (USA), the website from the TV news broadcasters, BBC and CNN as well as from weekly magazines such as Newsweek and Time, which serve the purpose of illustrating both the occurrence and usage of the PrP in different contexts. The period sampled refers to the years 2003-2008 and the range of topics and subgenres include hard news (current events and one-off unscheduled events called spot news) and soft news (longer featured articles on different issues which are not time-bound to immediacy). The research question investigated in the study is: what kind of functions emerge from the PrP samples in the language of news media? With respect to the question, the results indicate the PrP is a means of intensifying the information according to specific pragmatic needs the producer has while writing the piece of news. Therefore, this study brings an original contribution to the existing body of research on the expression of time in TESOL and Applied Linguistics / Esta pesquisa tem como objetivo descrever as funções do present perfect (PrP) que emergem do discurso jornalístico e traçar considerações discursivas e pedagógicas sobre essa questão. Optou-se pelo PrP, por ser um item da gramática da língua inglesa estudado sob diferentes perspectivas, por causa de sua complexidade tanto para os pesquisadores como para falantes não-nativos. A pesquisa lingüística acerca da natureza dos textos jornalísticos tem-se desenvolvido de modo abrangente, desde os anos de 1970, razão pela qual este trabalho, fundamentando-se na literatura da área, apresenta as visões de tempo verbal e aspecto, segundo Travaglia (1985) e Comrie (1985) e o uso do PrP, conforme os estudos de Schwenter (1994), Michaelis (1998), Engel & Ritz (2005) e Nishiyama & Koenig ( 2005, 2006). Esta revisão de literatura fornece uma perspectiva cronológica do que tem sido pesquisado sobre o uso do PrP e suas várias funções no discurso jornalístico, além de uma resenha dos autores sobre o discurso, dentre os quais, Bell (1991), Fowler (1991), Halliday (1978, 1985) e Fairclough (1995, 1999). Mais especificamente, fazendo uso da metodologia de pesquisa documental (Sanghera, 2002), analisam-se os dados coletados que incluem 60 textos de revistas e jornais da imprensa de qualidade americana e britânica, via mídia digital, The Guardian e The Independent (GB), The New York Times e The USA Today (EUA), os websites das redes de TV BBC e CNN e das revistas Newsweek e Time, com o propósito de ilustrar a ocorrência do PrP em diferentes contextos e assuntos. O período de coleta abrange os anos 2003 2008, e a diversidade de tópicos e subgêneros incluem Hard News (notícias atuais, como acidentes, e notícias acerca de política e diplomacia) e Soft News (artigos opinativos, não necessariamente relacionados a uma notícia recente). Em suma, procurou-se verificar que resultados indicam que o uso do PrP intensifica o valor da informação e atende às necessidades pragmáticas do produtor ao escrever o texto jornalístico e tentar dar uma contribuição original para as pesquisas que se direcionem à expressão da temporalidade no ensino de inglês como LE e para a Lingüística Aplicada no estudo do gênero notícia jornalística

Les travaux précédents menés en acquisition du langage soutiennent que les premières formes verbales de l’enfant sont limitées à l’expression de l’ici et maintenant (Weist, 1991). Cependant, une étude sur le développement du système verbal temporel en français (Parisse & Morgenstern, 2012) montre que l’enfant dispose d’une capacité à faire référence au passé de manière précoce, avant la production de marqueurs spécifiques dédiés à cet effet. Les études sur l’acquisition de l’aspect établissent une forte corrélation entre la production des verbes téliques et l’aspect perfectif (Shirai & Andersen, 1995), sans toutefois distinguer les marqueurs prétérit et present perfect. Slobin (1994) montre que le present perfect présente des fonctions communicatives spécifiques en lien avec l’expression du résultat et de l’expérience. À notre connaissance, aucune étude développementale de l’acquisition de ce marqueur n’a été menée jusqu’à présent. Nous nous proposons d’étudier les productions précoces de present perfect chez deux enfants britanniques dans le cadre des premiers usages des marqueurs de l’ici et maintenant et du décentrement dans le passé et de leurs valeurs dans le langage adressé à l’enfant. Nous avons mené des analyses quantitatives et qualitatives sur deux corpus longitudinaux denses d’interactions orales spontanées adulte/enfant (Tomasello, 2003). Nos résultats suggèrent que les productions précoces de present perfect résultent de la fréquence du marqueur trouvée chez l’adulte et du développement cognitif de l’enfant. L’étude des premiers usages du marqueur révèle que l’enfant s’appuie d’abord sur un état résultant visible à T0. Progressivement, l’enfant se sert de l’état résultant attaché à la production du marqueur pour verbaliser des attentes ou des intentions présupposées à T0. L’enfant demande ainsi à l’adulte de répondre à des besoins spécifiques exprimés dans la situation présente. / Previous studies in language acquisition have claimed that the verbal forms in early child language are limited to the expression of the here and now (Weist, 1991). However, a study of the verbal temporal system in French children’s speech (Parisse & Morgenstern, 2012) has shown that the children are able to refer to past events from an early age before they produce specific grammatical markers. Studies on the acquisition of aspect have established a strong correlation between the production of telic verbs and perfective aspect, without distinguishing between the present perfect and past tense. Slobin (1994) has shown that the first uses of the present perfect serve specific communicative functions that relate to the expression of result and experience. To our knowledge, no developmental study of the acquisition of the present perfect has been conducted so far. We conducted a study of how two British children use the present perfect in connection with their first uses of the markers referring to the here and now and their early productions of past tense. We examined the early uses of the markers in relation to the uses identified in the child directed speech in two dense oral corpora. Analyses based on qualitative and quantitative data were conducted on the adult and the child’s speech in the context of the interactions between the two (Tomasello, 2003). Our results suggest that the early productions of the present perfect result from the frequency of the marker found in the input and the cognitive development of the children. The study shows that they first rely on a visible resultant state in T0. Gradually, the children come to use the resultant state attached to the production of the marker to verbalise presupposed expectations or intentions in T0. By doing so, the children ask their caregivers to address specific needs that are expressed in the current situation.

This thesis deals with design algorithms for filter banks based on optimization. The design specifications consist of the perfect reconstruction and frequency response specifications for finite impulse response (FIR) analysis and synthesis filters. The perfect reconstruction conditions are formulated as a set of linear equations with respect to the analysis filters’ coefficients and the synthesis filters’ coefficients. Five design algorithms are presented. The first three are based on an unconstrained optimization of performance indices, which include the perfect reconstruction error and the error in the frequency specifications. The last two algorithms are formulated as constrained optimization problems with the perfect reconstruction error as the performance index and the frequency specifications as constraints. The performance of the five algorithms is evaluated and compared using six examples; these examples include uniform filter bank, compatible non-uniform filter bank and incompatible non-uniform filter bank designs. The evaluation criteria are based on distortion and aliasing errors, the magnitude response characteristics of analysis and synthesis filters, the computation time required for the optimization, and the convergence of the performance index with respect to the number of iterations. The results show that the five algorithms can achieve almost perfect reconstruction and can meet the frequency response specifications at an acceptable level. In the case of incompatible non-uniform filter banks, the algorithms have challenges to achieve almost perfect reconstruction. / Graduate

Almost p-ary perfect and nearly perfect sequences are equivalent to certain relative difference sets and direct product difference sets, respectively. This feature enables Chee, Tan and Zhou to determine the existence status of those sequences by using the tools of Design Theory. In particular, they determined the existence status of almost p-ary perfect and nearly perfect sequences of period n+1 for n 100, except some open cases in [6]. In this thesis, we obtained a set of Diophantine equations in integers while observing relative difference sets, and proved nonexistence of almost p-ary perfect sequences of period n + 1 for n (50,76,94,99,100).Also, we observed that it was possible to extend Diophantine equations that we used for relative difference sets to the direct product difference sets, thereby proved the nonexistence of almost p-ary nearly perfect sequences of type II of period n + 1 for p = 2, p = 3 and p = 5 at certain values of n. As a result, we answered two questions posed by Chee, Tan and Zhou in [6].

No description available.

Perfect Gibbs sampling is a method to turn Markov Chain Monte Carlo (MCMC) samplers into exact generators for independent random vectors. We show that a perfect Gibbs sampling algorithm suggested in the literature is not always generating from the correct distribution. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

In this work we investigate the use of perfect sampling methods within the context of Bayesian linear regression. We focus on inference problems related to the marginal posterior model probabilities. Model averaged inference for the response and Bayesian variable selection are considered. Perfect sampling is an alternate form of Markov chain Monte Carlo that generates exact sample points from the posterior of interest. This approach removes the need for burn-in assessment faced by traditional MCMC methods. For model averaged inference, we find the monotone Gibbs coupling from the past (CFTP) algorithm is the preferred choice. This requires the predictor matrix be orthogonal, preventing variable selection, but allowing model averaging for prediction of the response. Exploring choices of priors for the parameters in the Bayesian linear model, we investigate sufficiency for monotonicity assuming Gaussian errors. We discover that a number of other sufficient conditions exist, besides an orthogonal predictor matrix, for the construction of a monotone Gibbs Markov chain. Requiring an orthogonal predictor matrix, we investigate new methods of orthogonalizing the original predictor matrix. We find that a new method using the modified Gram-Schmidt orthogonalization procedure performs comparably with existing transformation methods, such as generalized principal components. Accounting for the effect of using an orthogonal predictor matrix, we discover that inference using model averaging for in-sample prediction of the response is comparable between the original and orthogonal predictor matrix. The Gibbs sampler is then investigated for sampling when using the original predictor matrix and the orthogonal predictor matrix. We find that a hybrid method, using a standard Gibbs sampler on the orthogonal space in conjunction with the monotone CFTP Gibbs sampler, provides the fastest computation and convergence to the posterior distribution. We conclude the hybrid approach should be used when the monotone Gibbs CFTP sampler becomes impractical, due to large backwards coupling times. We demonstrate large backwards coupling times occur when the sample size is close to the number of predictors, or when hyper-parameter choices increase model competition. The monotone Gibbs CFTP sampler should be taken advantage of when the backwards coupling time is small. For the problem of variable selection we turn to the exact version of the independent Metropolis-Hastings (IMH) algorithm. We reiterate the notion that the exact IMH sampler is redundant, being a needlessly complicated rejection sampler. We then determine a rejection sampler is feasible for variable selection when the sample size is close to the number of predictors and using Zellner’s prior with a small value for the hyper-parameter c. Finally, we use the example of simulating from the posterior of c conditional on a model to demonstrate how the use of an exact IMH view-point clarifies how the rejection sampler can be adapted to improve efficiency.

An aspect of the Romance languages that defies neat linguistic analysis is tense usage. In particular, students of Romance languages as well as grammarians have found it difficult to provide a consistent explanation for the imperfect - preterite opposition. Two main points of contention concern (i) the question of whether the two forms have an inherent aspectual content and (ii) the structure and role of lexical aspectual information in determining the overall meaning of a sentence. While the attempts at explaining French and Spanish usages of the imperfect and the preterite are numerous, hardly any work has been done in the interpretation of Romanian data. Furthermore, a general assumption that the same form - function opposition holds across Romance languages has led to cross-linguistic differences rarely being examined. I argue that the imperfect and the preterite do have an inherent aspectual content. However, in opposition to previous accounts, I maintain that the preterite does not provide a ‘closed’ viewpoint and that an atelic eventuality described by the verb phrase in the preterite can continue up to the present moment. I propose a description of the imperfect - preterite opposition that includes finer distinctions of lexical aspect based on its constituent stage structure. These finer lexical aspectual distinctions allow the identification of an area of divergence in the use of the two forms in French, Spanish, and Romanian: the preterite was found to be used more widely with states in Romanian than in French and Spanish.