Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Comunicação e Expressão. Programa de Pós-Graduação em Linguistica / Made available in DSpace on 2012-10-22T12:32:15Z (GMT). No. of bitstreams: 1 226909.pdf: 763472 bytes, checksum: 9ebeaab172853e9b1ae866024dcab01f (MD5) / Esta dissertação trata do item lexical tudo, na função de quantificador (Q), sendo norteada pelos seguintes objetivos: (a) analisar a multifuncionalidadede de tudo na língua falada de Florianópolis; e (b) investigar em que medida o item lexical tudo pode conter traços de definitude. A orientação teórica adotada é basicamente a do funcionalismo lingüístico givoniano, considerando-se ainda a noção de processos de referenciação e de instabilidade e estabilidade constitutivos da linguagem humana, além da noção semântica de especificidade. A análise é realizada a partir da relação estabelecida entre tudo e a entidade à qual está ligado no contexto discursivo. A multifuncionalidade desse item é mapeada hierarquicamente em termos de função > subfunções, identificadas a partir da relação fórica (direta e indireta) instaurada entre tudo e a entidade por ele quantificada. As subfunções identificadas para o quantificador são: (Q) super genérico, (Q) dêitico; (Q) imediato; (Q) anafórico; (Q) catafórico; e (Q) anafórico e catafórico - podendo agregar ainda certos tipos como: ampliador, resumitivo, enfatizador de atributos. A definitude, tratada como uma propriedade semântico-discursiva escalar, diz respeito às características da entidade quantificada por tudo, cujos traços constituintes envolvem as noções de referencialidade, determinação/delimitação e especificidade do que foi referido - além do papel do falante face à entidade quantificada. Propomos uma escala de definitude com seis graus, mostrando que o grau mais alto aproxima-se do conceito tradicional de pronome indefinido, com poucos dados de tudo nessa categoria; a maioria das ocorrências analisadas situa-se nos graus intermediários, evidenciando-se que tudo apresenta fortes traços de definitude.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro de Filosofia e Ciências Humanas, Programa de Pós-Graduação em Filosofia, Florianópolis, 2011 / Made available in DSpace on 2012-10-26T00:08:53Z (GMT). No. of bitstreams: 1 298844.pdf: 1033682 bytes, checksum: 1e055474d37fec3a08f9b42820f94431 (MD5) / Neste trabalho tratamos com alguns problemas filosóficos sugeridos pela mecânica quântica não-relativista. Nossa abordagem é formal, no sentido de que privilegiamos o estudo dos problemas em sistemas de lógica e teoria dos conjuntos convenientes, e que nossas sugestões para uma possível solução destes problemas deve ser buscada módulo uma determinada lógica. O tópico central unindo os capítulos consiste na alegada não-individualidade das partículas quânticas. Segundo alguns autores, as partículas com as quais trata a teoria não são indivíduos em nenhum sentido tradicional deste termo. Começamos esclarecendo o campo do debate, mostrando que de um ponto de vista ontológico, ou seja, da natureza das entidades com as quais a teoria está comprometida, temos o que se chama de subdeterminação da metafísica pela física: a teoria quântica por si só não nos fornece recursos para determinarmos se as partículas com as quais ela trata são indivíduos ou não indivíduos. Este é um tópico que deve ser decidido no campo da argumentação filosófica. Aqui, investigaremos como podemos dar um sentido rigoroso para a sugestão de que estas entidades são não-indivíduos introduzindo uma teoria de conjuntos que busca tratar com este tipo de entidades, a teoria de quase-conjuntos. No escopo desta teoria, não-indivíduos são representados como objetos para os quais a noção de identidade não se aplica com sentido. Nos capítulos seguintes apresentamos desenvolvimentos a partir deste ponto. Nossa primeira dificuldade consiste em se introduzir as noções de cardinalidade e contagem para não-indivíduos. Mostraremos como uma definição alternativa na teoria de quase-conjuntos pode ser apresentada com algumas das propriedades que se espera de uma definição de cardinal. Algumas objeções são estudadas e mostrarmos que não colocam obstáculos a este aspecto de nosso desenvolvimento. Assim, os conceitos de contagem, cardinalidade e individualidade podem ser mantidos separados. Na sequência argumentaremos que a própria noção de quantificação faz sentido quando tratamos de não-indivíduos, ou seja, podemos quantificar com sentido sobre entidades sem individualidade. Segundo alguns autores, a noção de quantificação, tão fundamental para o discurso ordinário, só faz sentido quando pressupomos que a identidade faz sentido para as entidades sobre as quais quantificamos. Argumentaremos que estas teses não se sustentam, e assim, que não constituem ameaça ao modo particular através do qual estamos compreendendo as partículas quânticas. Por fim apresentaremos um debate recente que busca estabelecer que as partículas quânticas devem obedecer ao Princípio de Identidade dos Indiscerníveis (PII), de modo que não podem ser não-indivíduos. Segundo este princípio, objetos diferindo numericamente possuem uma qualidade que os distingue. Não-indivíduos violam este princípio, eles são tais que podem de fato possuir todas as suas propriedades em comum sem serem numericamente o mesmo. Mostraremos que os argumentos apresentados em favor de PII em mecânica quântica dependem de que se aceite determinadas hipóteses metafísicas, no caso, que se aceite que relações podem ser utilizadas como estabelecendo discernibilidade qualitativa, algo que podemos rejeitar baseados em argumentos razoáveis. Concluímos o trabalho com um apêndice acerca de duas teorias clássicas da individualidade, a teoria de feixes e teoria do substrato, que são amplamente mencionadas no decorrer da tese mas que não são exploradas independentemente no corpo do texto.

ROCHA, T. A. Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes ⊕P e NP∩coNP através de lógicas com quantificadores de segunda ordem. 2014. 81 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T20:35:59Z No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-02-09T15:45:32Z (GMT) No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Made available in DSpace on 2015-02-09T15:45:32Z (GMT). No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) Previous issue date: 2014 / 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. / 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.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro de Comunicação e Expressão / Made available in DSpace on 2012-10-19T12:49:15Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-25T22:02:29Z : No. of bitstreams: 1 178680.pdf: 4527923 bytes, checksum: 37c4b76a3add24d16a994285e236034c (MD5) / Esta tese tem por objetivo examinar o estatuto semântico de sentenças com quantificação universal no PB, mostrando que há dois tipos de expressões universalmente quantificadas: a quantificação lawlike e a quantificação neutra para lawlikeness. Buscamos também dar um tratamento formal extensional ao quantificador universal do PB, que denominaremos aqui de TODO. Iniciamos argumentando que sentenças como 'Todo homem é canalha', por exemplo, não pode ser interpretada como uma sentença genérica (no sentido de Krifka et alli, 1995), 'Homem é canalha'. Apresentamos argumentos empíricos e estruturais que demonstram que o operador TODO não pode ser tomado pelo operador GEN, como poder-se-ia supor. Verificamos em nossa análise que há, de um lado, um tipo de sentença universal marcado que se caracteriza como sendo: +Lei; + restrito ao tipo de predicado; expressão de processos menos pontuais; marcado para a distributividade; - específico; + singular; - artigo definido; além disso, neste tipo de sentença universal o quantificador não flutua pela sentença. Por outro lado, há outro tipo de sentença universal no PB que é: ±Lei; - restrita ao tipo de predicado; expressão de processos ± pontuais; não-marcado para a distributividade; ± específico; - singular; + artigo definido; e que permite que o quantificador universal se desloque de sua posição inicial. Sugerimos que se trata de um só item lexical, mas que, por composicionalidade (no sentido de Pustejovsky, 1995), formam-se duas expressões semanticamente distintas de sentenças universais. Finalmente, apresentamos uma formalização para o TODO nos moldes da Teoria Mereológica, mostrando que o quantificador universal refere-se a elementos distintos de uma mereologia, conforme uma ou outra expressão de quantificação universal.

[pt] A quantização eficiente dos coeficientes do filtro de síntese utilizado em codificadores de voz CELP (Code Excited Linear Prediction) é fundamental para o bom desempenho desta classe de codificadores, especialmente quando se considera a operação em taxas inferiores a 8 Kbps. Neste trabalho são examinados três quantizadores vetoriais distintos que apresentam bom potencial para utilização em codificadores que operem a baixas taxas de bits. Cada um desses quantizadores foi implementado dentro da estrutura do codificador VSELP (Vector Sum Excited Linear Prediction) uma variação importante do codificador CELP padronizada para uso na telefonia celular digital americana. Estas três técnicas de quantização vetorial dos coeficientes do filtro baseiam-se na representação LSP e são comparadas em termos da robustez aos erros no canal de transmissão, da complexidade computacional de implementação e, principalmente, da qualidade da voz sintetizada (avaliada em função de medidas objetivas de razão sinal ruído ponderada e de testes de escuta informais). Também é examinada a aplicação da técnica de Simulated Annealing para associação de índices aos níveis de saída dos quantizadores, visando diminuir a sua sensibilidade aos erros no canal de transmissão. / [en] Efficent quantization of synthesis filter coefficients on CELP (Code Excited Linear Prediction) coders is very important for a good performance of this class of coders, specially when operating below 8 Kbps. Three vector quantizers with good potential for utilization on low rate coders are studied. Each of them was implemented inside the structure of VSELP( Vector Sum Linear Prediction) coder, an important menber in the class of CELP coders: VSELP is the north American cellular Communication standard. These three vector quantizers work with LSP parameters and are compared considering the robustness to channel errors, complexity and quality of sythesized speech. The quality of synthesized speech is evaluated considering objective measures of frequency weighted signal to noise ratio and subjective results obtained from informal listening tests. In order to improve the robustness to channel errors, the problem of binary indices assignment to the output levels of the quantizer is also investigated. The technique used to determine good indices assignments is Simulated Annealing

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Comunicação e Expressão. Programa de Pós-Graduação em Linguística / Made available in DSpace on 2012-10-18T01:48:17Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-25T17:39:30Z : No. of bitstreams: 1 182765.pdf: 1931747 bytes, checksum: 066d26d8519c7fdc3a51d77c435a4ff4 (MD5) / Análise da ordem variável do quantificador universal no sintagma nominal, verificando em que medida ocorre a influência de fatores lingüísticos e sociais sobre o uso de uma ou outra variante, estabelecendo algumas restrições que delimitam o contexto de variação. Para essa verificação, conciliamos a Sociolingüística Variacionista e a Gramática Gerativa com o intuito de explicar o fenômeno.

ROCHA, Thiago Alves. Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes ⊕P e NP∩coNP através de lógicas com quantificadores de segunda ordem. 2014. 81 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:02:32Z No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:36:28Z (GMT) No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Made available in DSpace on 2016-07-22T12:36:28Z (GMT). No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) Previous issue date: 2014 / 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. / 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.

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.

Esta pesquisa investiga o comportamento sintático dos quantificadores flutuantes no português brasileiro (PB), dentro do modelo teórico do Programa Minimalista (Chomsky 1995) da Sintaxe Gerativa, buscando atingir dois objetivos principais: (i) identificar as posições na sentença em que os quantificadores podem ou não flutuar e (ii) identificar a estrutura sintagmática interna das expressões quantificadas. Com Sportiche (1988) assumimos que a flutuação de quantificadores é derivada por movimentos sintáticos e com Valmala Elguea (2008) assumimos que este fenômeno é relacionado ao conteúdo informacional da sentença. Dessa forma, adotamos a cartografia de projeções informacionais (de tópico e foco) proposta por Rizzi (1997) para a periferia esquerda alta da sentença e por Belletti (2004) para a periferia esquerda baixa (acima de VP). Argumentando que é preciso distinguir os tipos categoriais dos quantificadores para explicar por que alguns são capazes de flutuar no interior da sentença e outros não, mostramos que os quantificadores que projetam a categoria QP, como cada (um) e todos, são capazes de flutuar, enquanto quantificadores que projetam uma categoria igual ou menor que DP, como muitos, poucos, vários e alguns, são incapazes de flutuar no PB. Mostramos ainda como as diferenças estruturais internas entre todos (cujo DP associado é um complemento de Q0) e cada (um) (cujo DP associado é analisado como um adjunto de QP) podem explicar seu comportamento distinto em relação a algumas possibilidades de flutuação, considerando o cálculo de Minimalidade Relativizada entre QP e DP. A flutuação de quantificadores é | 10 | analisada como resultado da interação entre a estrutura sintagmática interna de cada expressão quantificada e outras propriedades da gramática (universais e específicas da língua) operantes ao longo da derivação e envolvidas sobretudo na checagem de Caso e na satisfação dos Critérios de Tópico e Foco. As possibilidades de flutuação devem respeitar a assimetria entre a periferia esquerda alta e a periferia esquerda baixa do PB em relação ao licenciamento de elementos com ou sem Caso sintático: enquanto DPs, NumPs e NPs que não foram licenciados na sintaxe podem ser superficializados com Caso default na periferia alta, a periferia baixa apenas pode superficializar DPs, NumPs e NPs licenciados antes de Spell-Out. Assumimos que quantificadores de categoria QP, além de poderem ter seu Caso licenciado na sintaxe por checagem, podem se licenciar na superfície por Caso default ou por Transmissão de Caso seja na periferia alta, na periferia baixa ou na posição temática propriedade que lhes garante a capacidade de flutuação. Propomos uma análise uniforme em que estruturas flutuantes e não-flutuantes podem ser geradas a partir de um mesmo constituinte subjacente inserido na posição temática, sendo distintas por seu percurso derivacional. Dessa forma, esta análise simplifica e uniformiza algumas questões presentes na literatura sobre a flutuação de quantificadores. / This research investigates the syntactic behavior of floating quantifiers in Brazilian Portuguese (BP), in the framework of the Minimalist Program (Chomsky 1995), aiming at two main goals: (i) to identify the sentence positions in which quantifiers can or cannot float and (ii) to identify the internal phrase structure of quantified expressions. I assume with Sportiche (1988) that quantifier floating is derived through syntactic movement and with Valmala Elguea (2008) that this phenomenon is related to the informational content of the sentence. Thus, I adopt the cartography of informational projections (topic and focus) proposed by Rizzi (1997) for the high left periphery of the sentence and by Belletti (2004) for the low left periphery (above VP). I argue that in order to explain why some quantifiers are able to float inside the sentence and some are not, it is necessary to distinguish the categorial types of quantifiers. I show that quantifiers that project as QPs, like cada (um) each (one) and todos all, are able to float, whereas quantifiers that project as DPs or lower categories, like muitos many, poucos few, vários several and alguns some, are unable to float in BP. We also show how internal structural differences between todos (whose associate DP is a complement of Q0) and cada (um) (whose associate DP is analyzed as an adjunct of QP) can explain their different behavior regarding some floating possibilities, given the computation of Relativized Minimality between QP and DP. Quantifier floating is analyzed here as the result of the interaction between the internal phrase structure of each quantified expression and other properties of the grammar (both universal and language| 12 | specific), in particular Case-checking and Topic and Focus Criteria. Floating possibilities must respect the asymmetry between the high and the low left peripheries in BP regarding the licensing of elements with or without syntactic Case: whereas DPs, NumPs and NPs that have not been licensed in the syntax can surface with default Case in the high periphery, the low periphery can only host DPs, NumPs and NPs that have already been licensed before Spell- Out. I assume that QP-type quantifiers, besides being able to have their Case licensed in the syntax via Checking, can be licensed on the surface via default Case or Case Transmission regardless of whether they are in the high left periphery, in the low left periphery or in the thematic position which is in fact the property that provides them with the ability to float. We propose a uniform analysis in which both floated and non-floated structures can be generated from the same underlying constituent inserted in the thematic position, being distinguished by their derivational course. Therefore, this analysis simplifies and unifies some issues present in the literature on quantifier floating.

Esta pesquisa investiga o comportamento sintático dos quantificadores flutuantes no português brasileiro (PB), dentro do modelo teórico do Programa Minimalista (Chomsky 1995) da Sintaxe Gerativa, buscando atingir dois objetivos principais: (i) identificar as posições na sentença em que os quantificadores podem ou não flutuar e (ii) identificar a estrutura sintagmática interna das expressões quantificadas. Com Sportiche (1988) assumimos que a flutuação de quantificadores é derivada por movimentos sintáticos e com Valmala Elguea (2008) assumimos que este fenômeno é relacionado ao conteúdo informacional da sentença. Dessa forma, adotamos a cartografia de projeções informacionais (de tópico e foco) proposta por Rizzi (1997) para a periferia esquerda alta da sentença e por Belletti (2004) para a periferia esquerda baixa (acima de VP). Argumentando que é preciso distinguir os tipos categoriais dos quantificadores para explicar por que alguns são capazes de flutuar no interior da sentença e outros não, mostramos que os quantificadores que projetam a categoria QP, como cada (um) e todos, são capazes de flutuar, enquanto quantificadores que projetam uma categoria igual ou menor que DP, como muitos, poucos, vários e alguns, são incapazes de flutuar no PB. Mostramos ainda como as diferenças estruturais internas entre todos (cujo DP associado é um complemento de Q0) e cada (um) (cujo DP associado é analisado como um adjunto de QP) podem explicar seu comportamento distinto em relação a algumas possibilidades de flutuação, considerando o cálculo de Minimalidade Relativizada entre QP e DP. A flutuação de quantificadores é | 10 | analisada como resultado da interação entre a estrutura sintagmática interna de cada expressão quantificada e outras propriedades da gramática (universais e específicas da língua) operantes ao longo da derivação e envolvidas sobretudo na checagem de Caso e na satisfação dos Critérios de Tópico e Foco. As possibilidades de flutuação devem respeitar a assimetria entre a periferia esquerda alta e a periferia esquerda baixa do PB em relação ao licenciamento de elementos com ou sem Caso sintático: enquanto DPs, NumPs e NPs que não foram licenciados na sintaxe podem ser superficializados com Caso default na periferia alta, a periferia baixa apenas pode superficializar DPs, NumPs e NPs licenciados antes de Spell-Out. Assumimos que quantificadores de categoria QP, além de poderem ter seu Caso licenciado na sintaxe por checagem, podem se licenciar na superfície por Caso default ou por Transmissão de Caso seja na periferia alta, na periferia baixa ou na posição temática propriedade que lhes garante a capacidade de flutuação. Propomos uma análise uniforme em que estruturas flutuantes e não-flutuantes podem ser geradas a partir de um mesmo constituinte subjacente inserido na posição temática, sendo distintas por seu percurso derivacional. Dessa forma, esta análise simplifica e uniformiza algumas questões presentes na literatura sobre a flutuação de quantificadores. / This research investigates the syntactic behavior of floating quantifiers in Brazilian Portuguese (BP), in the framework of the Minimalist Program (Chomsky 1995), aiming at two main goals: (i) to identify the sentence positions in which quantifiers can or cannot float and (ii) to identify the internal phrase structure of quantified expressions. I assume with Sportiche (1988) that quantifier floating is derived through syntactic movement and with Valmala Elguea (2008) that this phenomenon is related to the informational content of the sentence. Thus, I adopt the cartography of informational projections (topic and focus) proposed by Rizzi (1997) for the high left periphery of the sentence and by Belletti (2004) for the low left periphery (above VP). I argue that in order to explain why some quantifiers are able to float inside the sentence and some are not, it is necessary to distinguish the categorial types of quantifiers. I show that quantifiers that project as QPs, like cada (um) each (one) and todos all, are able to float, whereas quantifiers that project as DPs or lower categories, like muitos many, poucos few, vários several and alguns some, are unable to float in BP. We also show how internal structural differences between todos (whose associate DP is a complement of Q0) and cada (um) (whose associate DP is analyzed as an adjunct of QP) can explain their different behavior regarding some floating possibilities, given the computation of Relativized Minimality between QP and DP. Quantifier floating is analyzed here as the result of the interaction between the internal phrase structure of each quantified expression and other properties of the grammar (both universal and language| 12 | specific), in particular Case-checking and Topic and Focus Criteria. Floating possibilities must respect the asymmetry between the high and the low left peripheries in BP regarding the licensing of elements with or without syntactic Case: whereas DPs, NumPs and NPs that have not been licensed in the syntax can surface with default Case in the high periphery, the low periphery can only host DPs, NumPs and NPs that have already been licensed before Spell- Out. I assume that QP-type quantifiers, besides being able to have their Case licensed in the syntax via Checking, can be licensed on the surface via default Case or Case Transmission regardless of whether they are in the high left periphery, in the low left periphery or in the thematic position which is in fact the property that provides them with the ability to float. We propose a uniform analysis in which both floated and non-floated structures can be generated from the same underlying constituent inserted in the thematic position, being distinguished by their derivational course. Therefore, this analysis simplifies and unifies some issues present in the literature on quantifier floating.