abstract: Many neurological disorders, especially those that result in dementia, impact speech and language production. A number of studies have shown that there exist subtle changes in linguistic complexity in these individuals that precede disease onset. However, these studies are conducted on controlled speech samples from a specific task. This thesis explores the possibility of using natural language processing in order to detect declining linguistic complexity from more natural discourse. We use existing data from public figures suspected (or at risk) of suffering from cognitive-linguistic decline, downloaded from the Internet, to detect changes in linguistic complexity. In particular, we focus on two case studies. The first case study analyzes President Ronald Reagan’s transcribed spontaneous speech samples during his presidency. President Reagan was diagnosed with Alzheimer’s disease in 1994, however my results showed declining linguistic complexity during the span of the 8 years he was in office. President George Herbert Walker Bush, who has no known diagnosis of Alzheimer’s disease, shows no decline in the same measures. In the second case study, we analyze transcribed spontaneous speech samples from the news conferences of 10 current NFL players and 18 non-player personnel since 2007. The non-player personnel have never played professional football. Longitudinal analysis of linguistic complexity showed contrasting patterns in the two groups. The majority (6 of 10) of current players showed decline in at least one measure of linguistic complexity over time. In contrast, the majority (11 out of 18) of non-player personnel showed an increase in at least one linguistic complexity measure. / Dissertation/Thesis / Masters Thesis Computer Science 2016

As recentes inovações em técnicas de Aprendizado de Máquina levaram a uma ampla utilização de modelos inteligentes para resolver problemas complexos que são especialmente difíceis de computar com algoritmos e estruturas de dados convencionais. Em particular, pesquisas recentes em Processamento de Imagens e Vídeo mostram que é possível desenvolver modelos de Aprendizado de Máquina que realizam reconhecimento de objetos e até mesmo de ações com altos graus de confiança. Além disso, os últimos avanços em algoritmos de treinamento para Redes Neurais Profundas (Deep Learning Neural Networks) estabeleceram um importante marco no estudo de Aprendizado de Máquina, levando a descobertas promissoras em Visão Computacional e outras aplicações. Estudos recentes apontam que também é possível desenvolver modelos inteligentes capazes de reduzir drasticamente o espaço de otimização do modo de decisão em codificadores de vídeo com perdas irrelevantes em eficiência de compressão. Todos esses fatos indicam que Aprendizado de Máquina para redução de complexidade em aplicações de vídeo é uma área promissora para pesquisa. O objetivo desta tese é investigar técnicas baseadas em aprendizado para reduzir a complexidade das decisões da codificação HEVC, com foco em aplicações de codificação e transcodificação rápidas. Um perfilamento da complexidade em codificadores é inicialmente apresentado, a fim de identificar as tarefas que requerem prioridade para atingir o objetivo dessa tese. A partir disso, diversas variáveis e métricas são extraídas durante os processos de codificação e decodificação para avaliar a correlação entre essas variáveis e as decisões de codificação associadas a essas tarefas. Em seguida, técnicas de Aprendizado de Máquina são empregadas para construir classificadores que utilizam a informação coletada para prever o resultado dessas decisões, eliminando o custo computacional necessário para computá-las. As soluções de codificação e transcodificação foram desenvolvidas separadamente, pois o tipo de informação é diferente em cada caso, mas a mesma metologia foi aplicada em ambos os casos. Além disso, mecanismos de complexidade escalável foram desenvolvidos para permitir o melhor desempenho taxa-compressão para um dado valor de redução de complexidade. Resultados experimentais apontam que as soluções desenvolvidas para codificação rápida atingiram reduções de complexidade entre 37% e 78% na média, com perdas de qualidade entre 0.04% e 4.8% (medidos em Bjontegaard Delta Bitrate – BD-BR). Já as soluções para trancodificação rápida apresentaram uma redução de 43% até 67% na complexidade, com BD-BR entre 0.34% e 1.7% na média. Comparações com o estado da arte confirmam a eficácia dos métodos desenvolvidos, visto que são capazes de superar os resultados atingidos por soluções similares. / The recent innovations in Machine Learning techniques have led to a large utilization of intelligent models to solve complex problems that are especially hard to compute with traditional data structures and algorithms. In particular, the current research on Image and Video Processing shows that it is possible to design Machine Learning models that perform object recognition and even action recognition with high confidence levels. In addition, the latest progress on training algorithms for Deep Learning Neural Networks was also an important milestone in Machine Learning, leading to prominent discoveries in Computer Vision and other applications. Recent studies have also shown that it is possible to design intelligent models capable of drastically reducing the optimization space of mode decision in video encoders with minor losses in coding efficiency. All these facts indicate that Machine Learning for complexity reduction in visual applications is a very promising field of study. The goal of this thesis is to investigate learning-based techniques to reduce the complexity of the HEVC encoding decisions, focusing on fast video encoding and transcoding applications. A complexity profiling of HEVC is first presented to identify the tasks that must be prioritized to accomplish our objective. Several variables and metrics are then extracted during the encoding and decoding processes to assess their correlation with the encoding decisions associated with these tasks. Next, Machine Learning techniques are employed to construct classifiers that make use of this information to accurately predict the outcome of these decisions, eliminating the timeconsuming operations required to compute them. The fast encoding and transcoding solutions were developed separately, as the source of information is different on each case, but the same methodology was followed in both cases. In addition, mechanisms for complexity scalability were developed to provide the best rate-distortion performance given a target complexity reduction. Experimental results demonstrated that the designed fast encoding solutions achieve time savings of 37% up to 78% on average, with Bjontegaard Delta Bitrate (BD-BR) increments between 0.04% and 4.8%. In the transcoding results, a complexity reduction ranging from 43% to 67% was observed, with average BD-BR increments from 0.34% up to 1.7%. Comparisons with state of the art confirm the efficacy of the designed methods, as they outperform the results achieved by related solutions.

Codificadores HEVC impõem diversos desafios em aplicações embarcadas com restrições computacionais, especialmente quando há restrições de processamento em tempo real. Para tornar a codificação de vídeos HEVC factível nessas situações, é proposto neste trabalho um Sistema de Controle de Complexidade (SCC) que se adapta dinamicamente a capacidades computacionais varáveis. Considera-se que o codificador faz parte de um sistema maior, o qual informa suas restrições como disponibilidade da CPU e processamento alvo para o SCC. Para desenvolver um sistema eficiente, uma extensiva análise de complexidade dos principais parâmetros de codificação é realizada. Nessa análise, foi definida uma métrica livre de particularidades da plataforma de simulação, como hierarquia de memória e acesso concorrente à unidade de processamento. Essa métrica foi chamada de Complexidade Aritmética e pode ser facilmente adaptada para diversas plataformas. Os resultados mostram que o SCC proposto atinge ganhos médios de 40% em complexidade com penalidade mínima em eficiência de compressão e qualidade. As análises de adaptabilidade e controlabilidade mostraram que o SCC rapidamente se adapta a diferentes restrições, por exemplo, quando a disponibilidade de recursos computacionais varia dinamicamente enquanto um vídeo é codificado. Comparado com o estado da arte, o SCC atinge uma redução de 44% no tempo de codificação com penalidade de 2.9% na taxa de compressão e acréscimo de 6% em BD-bitrate. / HEVC encoders impose several challenges in resource-/computationally-constrained embedded applications, especially under real-time throughput constraints. To make HEVC encoding feasible in such scenarios, an adaptive Computation Management Scheme (CMS) that dynamically adapts to varying compute capabilities is proposed in this work. It is assumed that the encoder is part of a larger system, which informs to the CMS its restrictions and requirements, like CPU availability and target frame rate. To effectively develop and apply such a scheme, an extensive computational effort analysis of key encoding parameters of the HEVC is carried out. For this analysis, a platform-orthogonal metric called “Arithmetic Complexity” was developed, which can be widely adopted for various computing platforms. The achieved results illustrate that the proposed CMS provides 40% cycle savings on average at the cost of small RD penalties. The adaptability and controllability analyses show that the CMS quickly adapts to different constrained scenarios, e.g., when the executing HEVC encoder requires more or less computation from the underlying platform. Compared to state of the art, the CMS achieves 44% encoding time savings while incurring a minor 2.9% increase in the bitrate and 6% increase in BD-bitrate.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / VÃrios problemas computÃveis podem ser resolvidos de maneira mais eficiente ou mais natural atravÃs de algoritmos probabilÃsticos, o que mostra que o uso de tais algoritmos à bastante relevante em computaÃÃo. Entretanto, os algoritmos probabilÃsticos podem retornar uma resposta errada com uma certa probabilidade. Observe, ainda que o uso de algoritmos probabilÃsticos nÃo resolve problemas nÃo computÃveis. A Complexidade Computacional caracteriza a complexidade de um problema a partir da quantidade de recursos computacionais, como espaÃo e tempo, para resolvÃ-lo. Problemas que tem a mesma complexidade compÃem uma classe. As classes de complexidade computacional sÃo relacionadas atravÃs de uma hierarquia. A Complexidade Descritiva usa lÃgicas para expressar os problemas e capturar classes de complexidade computacional no sentido de expressar todos, e apenas, os problemas desta classe. Dessa forma, a complexidade de um problema nÃo depende de fatores fÃsicos, como tempo e espaÃo, mas apenas da expressividade da lÃgica que o define. Resultados importantes da Ãrea mostraram que vÃrias classes de complexidade computacional podem ser caracterizadas por lÃgicas. Por exemplo, a classe NP foi mostrada equivalente à classe dos problemas expressos pelo fragmento existencial da LÃgica de Segunda Ordem. Este estreito relacionamento entre tais Ãreas permite que alguns resultados da Ãrea de LÃgica sejam transferidos para a de Complexidade Computacional e vice-versa. Apesar da importÃncia de algoritmos probabilÃsticos e da Complexidade Descritiva, existem poucos resultados de caracterizaÃÃo, por lÃgicas, das classes de complexidade computacional probabilÃsticas. Neste trabalho, buscamos mostrar caracterizaÃÃes para cada uma das classes de complexidade probabilÃsticas de tempo polinomial. Nos nossos resultados, utilizamos quantificadores generalizados de segunda ordem para simular a aceitaÃÃo das mÃquinas nÃo-determinÃsticas dessas classes. Achamos caracterizaÃÃes lÃgicas na literatura apenas para as classes PP e BPP. No primeiro caso, a lÃgica utilizada era a de primeira ordem adicionada de um quantificador maioria de segunda ordem. Com a abordagem criada neste trabalho, conseguimos obter uma prova alternativa para a caracterizaÃÃo de PP. Com essa mesma metodologia, tambÃm conseguimos caracterizar a classe ⊕P atravÃs de uma lÃgica com um quantificador de paridade. No caso de BPP, existia um resultado que utilizava uma lÃgica com semÃntica probabilÃstica. Usando nossa abordagem de quantificadores generalizados, conseguimos obter uma caracterizaÃÃo alternativa para essa classe. Com o mesmo mÃtodo, conseguimos caracterizar as classes probabilÃsticas semÃnticas RP, coRP, ZPP e a classe semÃntica NP∩coNP. Por fim, mostramos uma aplicaÃÃo dos resultados de Complexidade Descritiva na criaÃÃo de algoritmos atravÃs de uma especificaÃÃo lÃgica. / Many computable problems can be solved more efficiently or in a more natural way through probabilistic algorithms, which shows that the use of such algorithms is quite relevant in Computer Science. However, probabilistic algorithms may return a wrong answer with a certain probability. Also, the use of probabilistic algorithms does not solve problems that are not computable. In Computational Complexity, the complexity of a problem is characterized based on the amount of computational resources, such as space and time, needed to solve it. Problems that have the same complexity compose the same class. The computational complexity classes are related by a hierarchy. In Descriptive Complexity, a logic is used to express problems and capture computational complexity classes in order to express all and only the problems of this class. Thus, the complexity of a problem does not depend on physical factors, such as time and space, but only on the expressiveness of the logic that defines it. Important results of the area states that several classes of computational complexity can be characterized by a logic. For example, the class NP has been shown equivalent to the class of problems expressed by the existential fragment of Second-Order Logic. This close relationship between these areas allows some results about Logics to be transferred to Computational Complexity and vice versa. Despite of the importance of probabilistic algorithms and of Descriptive Complexity, there are few results on the characterization, by a logic, of probabilistic computational complexity classes. In this work, we show characterizations for each of the polinomial time probabilistic complexity classes. In our results, we use second-order generalized quantifiers to simulate the acceptance of the nondeterministic machines of these classes. We found Logical characterizations in the literature only for classes PP and BPP. In the first case, the logic employed was the first-order added by a quantifier most of second-order. With the approach established in this work, we obtain an alternative proof for the characterization of PP. With the same methodology, we also characterize the class ⊕P through a logic with a second-order parity quantifier. In the case of BPP , there was a result that used a logic with probabilistic semantics. Using our approach of generalized quantifiers, we obtain an alternative characterization for this class. With the same method, we were able to characterize the probabilistic semantic classes RP, coRP, ZPP and the semantic class NP ∩ coNP. Finally, we show an application of Descriptive Complexity results in the creation of algorithms from a logic specification.

Codificadores HEVC impõem diversos desafios em aplicações embarcadas com restrições computacionais, especialmente quando há restrições de processamento em tempo real. Para tornar a codificação de vídeos HEVC factível nessas situações, é proposto neste trabalho um Sistema de Controle de Complexidade (SCC) que se adapta dinamicamente a capacidades computacionais varáveis. Considera-se que o codificador faz parte de um sistema maior, o qual informa suas restrições como disponibilidade da CPU e processamento alvo para o SCC. Para desenvolver um sistema eficiente, uma extensiva análise de complexidade dos principais parâmetros de codificação é realizada. Nessa análise, foi definida uma métrica livre de particularidades da plataforma de simulação, como hierarquia de memória e acesso concorrente à unidade de processamento. Essa métrica foi chamada de Complexidade Aritmética e pode ser facilmente adaptada para diversas plataformas. Os resultados mostram que o SCC proposto atinge ganhos médios de 40% em complexidade com penalidade mínima em eficiência de compressão e qualidade. As análises de adaptabilidade e controlabilidade mostraram que o SCC rapidamente se adapta a diferentes restrições, por exemplo, quando a disponibilidade de recursos computacionais varia dinamicamente enquanto um vídeo é codificado. Comparado com o estado da arte, o SCC atinge uma redução de 44% no tempo de codificação com penalidade de 2.9% na taxa de compressão e acréscimo de 6% em BD-bitrate. / HEVC encoders impose several challenges in resource-/computationally-constrained embedded applications, especially under real-time throughput constraints. To make HEVC encoding feasible in such scenarios, an adaptive Computation Management Scheme (CMS) that dynamically adapts to varying compute capabilities is proposed in this work. It is assumed that the encoder is part of a larger system, which informs to the CMS its restrictions and requirements, like CPU availability and target frame rate. To effectively develop and apply such a scheme, an extensive computational effort analysis of key encoding parameters of the HEVC is carried out. For this analysis, a platform-orthogonal metric called “Arithmetic Complexity” was developed, which can be widely adopted for various computing platforms. The achieved results illustrate that the proposed CMS provides 40% cycle savings on average at the cost of small RD penalties. The adaptability and controllability analyses show that the CMS quickly adapts to different constrained scenarios, e.g., when the executing HEVC encoder requires more or less computation from the underlying platform. Compared to state of the art, the CMS achieves 44% encoding time savings while incurring a minor 2.9% increase in the bitrate and 6% increase in BD-bitrate.

All over the world, firms and governments are increasingly concerned about the rise in tax complexity. To manage it and develop effective simplification measures, detailed information on the current drivers of complexity is required. However, research on this topic is scarce. This is surprising as the latest developments - for example, triggered by the BEPS project - give rise to the conjecture that complexity drivers may have changed, thus questioning the findings of prior studies. In this paper, we shed light on this issue and provide a global picture of the current drivers of tax complexity that multinational corporations face based on a survey of 221 highly experienced tax practitioners from 108 countries. Our results show that prior complexity drivers of the tax code are still relevant, with details and changes of tax regulations being the two most influential complexity drivers. We also find evidence for new relevant complexity drivers emerging from different areas of the tax framework, such as inconsistent decisions among tax officers (tax audits) or retroactively applied tax law amendments (tax enactment). Based on the responses of the practitioners, we develop a concept of tax complexity that distinguishes two pillars, tax code and tax framework complexity, and illustrates the various aspects that should be considered when assessing the complexity of a country's tax system. / Series: WU International Taxation Research Paper Series

Codificadores HEVC impõem diversos desafios em aplicações embarcadas com restrições computacionais, especialmente quando há restrições de processamento em tempo real. Para tornar a codificação de vídeos HEVC factível nessas situações, é proposto neste trabalho um Sistema de Controle de Complexidade (SCC) que se adapta dinamicamente a capacidades computacionais varáveis. Considera-se que o codificador faz parte de um sistema maior, o qual informa suas restrições como disponibilidade da CPU e processamento alvo para o SCC. Para desenvolver um sistema eficiente, uma extensiva análise de complexidade dos principais parâmetros de codificação é realizada. Nessa análise, foi definida uma métrica livre de particularidades da plataforma de simulação, como hierarquia de memória e acesso concorrente à unidade de processamento. Essa métrica foi chamada de Complexidade Aritmética e pode ser facilmente adaptada para diversas plataformas. Os resultados mostram que o SCC proposto atinge ganhos médios de 40% em complexidade com penalidade mínima em eficiência de compressão e qualidade. As análises de adaptabilidade e controlabilidade mostraram que o SCC rapidamente se adapta a diferentes restrições, por exemplo, quando a disponibilidade de recursos computacionais varia dinamicamente enquanto um vídeo é codificado. Comparado com o estado da arte, o SCC atinge uma redução de 44% no tempo de codificação com penalidade de 2.9% na taxa de compressão e acréscimo de 6% em BD-bitrate. / HEVC encoders impose several challenges in resource-/computationally-constrained embedded applications, especially under real-time throughput constraints. To make HEVC encoding feasible in such scenarios, an adaptive Computation Management Scheme (CMS) that dynamically adapts to varying compute capabilities is proposed in this work. It is assumed that the encoder is part of a larger system, which informs to the CMS its restrictions and requirements, like CPU availability and target frame rate. To effectively develop and apply such a scheme, an extensive computational effort analysis of key encoding parameters of the HEVC is carried out. For this analysis, a platform-orthogonal metric called “Arithmetic Complexity” was developed, which can be widely adopted for various computing platforms. The achieved results illustrate that the proposed CMS provides 40% cycle savings on average at the cost of small RD penalties. The adaptability and controllability analyses show that the CMS quickly adapts to different constrained scenarios, e.g., when the executing HEVC encoder requires more or less computation from the underlying platform. Compared to state of the art, the CMS achieves 44% encoding time savings while incurring a minor 2.9% increase in the bitrate and 6% increase in BD-bitrate.

<p>In the thesis we are concerned with actual problems on palindromic subwords and palindromic factors of finite and infinite words. The main course of the research are the ways of determining which of two given words is &ldquo;more palindromic&rdquo; than the other one, that is, defining a measure for the degree of &ldquo;palindromicity&rdquo; of a word. Particularly, we pay attention to two actual approaches: the so-called MP-ratio and the so-called <em>palindromic defect</em>, and answer several open questions about them.<br /><br />Namely, concerning the MP-ratio, a few plausible-looking question have been asked in the literature, which would have, if answered positively, made computations of MP-ratios significantly simpler. We add one more related question to these ones, and then show that, rather unexpectedly, all these questions have negative answer.<br /><br />Concerning the palindromic defect, the main result of this work is a construction of an infinite class of infinite words that have several properties that were sought after in some recent works in this area. Among the most interesting facts is that that all these words are aperiodic words of a finite positive defect, having the set of factors closed under reversal---in some recent works, the construction of even a single word having these properties turned out to be quite hard. Using these words, which we are calling <em>highly potential words</em>, we check the validity of several open&nbsp; conjectures, and for several of them we find out that they are false.</p> / <p> U tezi razmatramo aktuelne probleme u vezi s palindromskim podrečima i palindromskim faktorima konačnih i beskonačnih reči. Glavni pravac istraživanja jesu kriterijumi za određivanje koja od dve date reči je &bdquo;palindromičnija&ldquo; od druge, tj. određivanje stepena &bdquo;palindromičnosti&ldquo; date reči. Akcenat stavljamo na dva aktuelna pristupa: tzv. <em>MP-razmeru</em> i tzv. <em>palindromski defekt</em>, i odgovaramo na vi&scaron;e otvorenih pitanja u vezi s njima.<br /> <br /> Naime, u vezi sa MP-razmerom u literaturi je postavljeno vi&scaron;e pitanja, intuitivno uverljivih, koja bi, u slučaju pozitivnog razre&scaron;enja, znatno pojednostavila izračunavanje MP-razmere. Ovim pitanjima dodajemo jo&scaron; jedno srodno, a zatim pokazujemo da, prilično neočekivano, sva ova pitanja imaju negativan odgovor.<br /> <br /> U vezi s palindromskim defektom, glavni rezultat rada je konstrukcija beskonačne klase beskonačnih reči koje imaju vi&scaron;e osobina za kojima je iskazana potreba u skora&scaron;njim radovima iz ove oblasti. Među najzanimljivije spada činjenica da su sve aperiodične reči konačnog pozitivnog defekta, i da im je skup faktora zatvoren za preokretanje &ndash; u nekim skora&scaron;njim radovima konstrukcija makar jedne reči s ovim osobinama pokazala se kao prilično te&scaron;ka. Pomoću ovih reči, koje nazivamo <em>visokopotencijalne reči</em>, ispitujemo validnost vi&scaron;e otvorenih hipoteza, i za vi&scaron;e njih ustanovljavamo da nisu validne.</p>

No description available.

Research has shown that children with Language Impairment (LI) struggle with social communication skills in addition to their characteristic syntactic difficulties. This pilot study analyzed the potential change in grammatical complexity in narratives of five children with LI when enrolled in a social communication intervention. The intervention itself focused on teaching emotion understanding by reading and reenacting children’s stories and journaling. Grammatical limitations were indirectly addressed by clinician modeling of complex forms during the intervention sessions. Each child’s productions were assessed and analyzed for grammatical complexity during retelling a book in the Mercer Mayer “a boy, a dog, and a frog” series. The children performed this task once a week during the course of the intervention. Specific measures used included the average length of terminable unit (T-unit) and the number of subordinate clauses used in each narrative. Three students’ productions remained steady throughout the course of the interventions; their grammatical complexity neither increased nor decreased. One student’s production showed a clear decrease in complexity but was explained by an obvious and arguably more creative change in her language output. One student’s grammatical complexity increased throughout the sessions as indicated by a steady increase in the average length of T-unit. Thus, the results of this study were equivocal. There were several limitations, however, that might be addressed in future intervention studies.