This dissertation argues for the existence of functional attitude predicates, light attitudes, such as light say and light see. Two phenomena are identified as functional attitudes: evidentiality and logophoric say-complementizers. I propose that reportative evidential markers and logophoric licensing complementizers are cross-linguistic variations of overt morphosyntactic realizations of the same light attitude: a functionalized predicate say. The parallel between evidentiality and logophoricity drawn here highlights their properties that have not been discussed or formally accounted for until now, and explains why they are in a typological complementary distribution across the world's languages. At the same time, direct and reportative evidentials even within the same language exhibit a number of syntactic and semantic differences that have not been noticed in the literature before. I derive them from the analysis of reportative and direct evidentials as different kinds of functional predicates: say and perceive, respectively. After establishing the nature of evidentials, I develop their syntactic and semantic properties formally. I claim that light attitudes are hosted by a projection cP, which selects CP and has properties similar to that of the light verb projection vP, such as argument structure, thematic roles, and `flavors'. The semantic composition of light attitudes is based on that of lexical attitudes, for which I am following and expanding ideas from de-compositional semantics. This allows for a simple and conceptually motivated analysis that does not need any additional theoretical primitives. I develop novel methodology to test for evidential challengeability and newness of evidentials that take the between-evidential differences into account. The results support the representation of the evidential contribution as a presupposition.

<p> Propositional proof complexity is a field of theoretical computer science which concerns itself with the lengths of formal proofs in various propositional proof systems. Frege systems are an important class of propositional proof systems. Extended Frege augments them by allowing the introduction of new variables to abbreviate formulas. Perhaps the largest open question in propositional proof complexity is whether or not Extended Frege is significantly more powerful that Frege. Several proof systems, each introducing new rules or syntax to Frege, have been developed in an attempt to shed some light on this problem.</p> <p> We introduce one such system, which we call H, which allows for the quantification of transpositions of propositional variables. We show that H is sound and complete, and that H's transposition quantifiers efficiently represent any permutation.</p> <p> The most important contribution is showing that a fragment of this proof system, H*1, is equivalent in power to Extended Frege. This is a complicated and rather technical result, and is achieved by showing that H*1 can efficiently prove translations of the first-order logical theory ∀PLA, a logical theory well suited for reasoning about linear algebra and properties of graphs.</p> / Thesis / Master of Science (MSc)

Object-oriented programming languages all involve the notions of class and object. We extend the notion of class so that any Boolean combination of classes is also a class. Boolean classes allow greater precision and conciseness in naming the class of objects governed by a particular method. A class can be viewed as a predicate which is either true or false of any given object. Unlike predicates however classes have an inheritance hierarchy which is known at compile time. Boolean classes extend the notion of class, making classes more like predicates, while preserving the compile time computable inheritance hierarchy.

We explore the relationships between the computational problem of recognizing expander graphs, and the problem of efficiently approximating proof length in the well-known system of \emph{resolution}. This program builds upon known connections between graph expansion and resolution lower bounds. A proof system $P$ is \emph{(quasi-)automatizable} if there is a search algorithm which finds a $P$-proof of a given formula $f$ in time (quasi)polynomial in the length of a shortest $P$-proof of $f$. It is open whether resolution is (quasi-)automatizable. We prove several conditional non-automatizability results for resolution modulo new conjectures concerning the complexity of identifying bipartite expander graphs. Our reductions use a natural family of formulas and exploit the well-known relationships between expansion and length of resolution proofs. Our hardness assumptions are unsupported; we survey known results as progress towards establishing their plausibility. The major contribution is a conditional hardness result for the quasi-automatizability of resolution.

We explore the relationships between the computational problem of recognizing expander graphs, and the problem of efficiently approximating proof length in the well-known system of \emph{resolution}. This program builds upon known connections between graph expansion and resolution lower bounds. A proof system $P$ is \emph{(quasi-)automatizable} if there is a search algorithm which finds a $P$-proof of a given formula $f$ in time (quasi)polynomial in the length of a shortest $P$-proof of $f$. It is open whether resolution is (quasi-)automatizable. We prove several conditional non-automatizability results for resolution modulo new conjectures concerning the complexity of identifying bipartite expander graphs. Our reductions use a natural family of formulas and exploit the well-known relationships between expansion and length of resolution proofs. Our hardness assumptions are unsupported; we survey known results as progress towards establishing their plausibility. The major contribution is a conditional hardness result for the quasi-automatizability of resolution.

The goal of data mining is to help market managers find relationships among items from large datasets to increase profits. Among the mining techniques, the Apriori algorithm is the most basic and important for association rule mining. Although a lot of mining approaches have been proposed based on the Apriori algorithm, most of them focus on positive association rules, such as R1: ¡§If milk is bought, then bread is bought¡¨. However, rule R1 may confuses users and makes wrong decision if the negative relation rules are not considered. For example, the rule such as R2: ¡§If milk is not bought, then bread is bought¡¨ may also be found. Then, the rule R2 conflicts with the positive rule R1. So, if two rules such as ¡§If milk is bought, then bread is bought¡¨ and ¡§If milk is not bought, then bread is not bought¡¨ are found at the same time, the rules which is called coherent rule may be more valuable.In this thesis, we thus propose two algorithms for solving this problem. The first proposed algorithm is named Highly Coherent Rule Mining algorithm (HCRM), which takes the properties of propositional logic into consideration and is based on Apriori approach for finding coherent rules. The lower and upper bounds of itemsets are also tightened to remove unnecessary check. Besides, in order to improve the efficiency of the mining process, the second algorithm, namely Projection-based Coherent Mining Algorithm (PCA), based on data projection is proposed for speeding up the execution time. Experiments are conducted on real and simulation datasets to demonstrate the performance of the proposed approaches and the results show that both HCRM and PCA can find more reliable rules and PCA is more efficient.

[pt] Neste trabalho investigou-se o emprego dos recentes algoritmos de minimização de funções não diferenciáveis para a resolução do problema da síntese de filtros digitais FIR de fase não linear. O problema desta síntese correspondente a um problema de Aproximações de Funções quando o domínio e o contradomínio da função são corpos diferentes, i.e. real e complexo respectivamente. Serão revistos definições e propriedades dos filtros FIR, as técnicas de síntese para o caso de resposta de fase linear e não linear, para a seguir, apresentar a teoria e implementação da Otimização de Funções não Diferenciáveis. Exemplos e extensões desta teoria também serão apresentados. / [en] This work will describes the use of the recent techniques of non smooth optimization to the synthesis of non-linear phase FIR filters. The problem of such synthesis corresponds to a problem of Approximation of Functions when the domain and the image sets of the function are different fields, i.e. real and complex respectively. A revision of the theory of FIR filters with a survey of the linear and non linear phase usual synthesis non-smooth optimization theory and implementation. Together with design examples will follow. An extension of these theories will be suggested.

O uso adequado de ambientes computacionais pode representar um aumento de qualidade e conforto no processo de ensino-aprendizagem de algumas disciplinas. Percebeu-se, através de pesquisa, a inexistência de ferramentas voltadas para o ensino-aprendizagem de cálculo proposicional que atendessem aos critérios estabelecidos para um ambiente de suporte ao aluno (ASA). Como consequência do resultado da pesquisa, este trabalho introduz o conceito e os requisitos básicos de um ASA, concebe e implementa uma ferramenta ASA voltada para o ensino-aprendizagem de cálculo proposicional, acompanhada de um plano de ensino opcional, e os coloca à disposição da comunidade acadêmica. Apresenta também estudos de casos sobre apresentações e usos da ferramenta em vários estágios de desenvolvimento, além da descrição de cada módulo e dos métodos e regras disponibilizados pela ferramenta. Pretende-se que a ferramenta ASA-CalcPro e o plano de ensino sugerido, sejam uma contribuição social positiva e um estímulo ao ensino-aprendizagem de cálculo proposicional. / The adequate use of computational environments can increase the quality and comfort of the teaching-learning process for some of the academic disciplines. A review of the literature reveals the lack of existing tools for the teaching-learning of the propositional calculus that conform to the criteria established for the student support environment (ambiente de suporte ao aluno (ASA)). As a consequence of this conclusion, the current thesis introduces the concept of, and the basic requirements for, an ASA, conceives and implements an ASA tool for the teaching-learning of the propositional calculus, together with an optional teaching plan, and puts both at the disposition of the academic community. The thesis also presents case studies of presentations and uses of the tool at various stages of its development, as well as a description of each module and of the methods and rules made available for use by the tool. It is hoped that the ASA-CalcPro tool and the suggested plan of study will make a positive social contribution and will be a stimulant for the teaching-learning of the propositional calculus.

O uso adequado de ambientes computacionais pode representar um aumento de qualidade e conforto no processo de ensino-aprendizagem de algumas disciplinas. Percebeu-se, através de pesquisa, a inexistência de ferramentas voltadas para o ensino-aprendizagem de cálculo proposicional que atendessem aos critérios estabelecidos para um ambiente de suporte ao aluno (ASA). Como consequência do resultado da pesquisa, este trabalho introduz o conceito e os requisitos básicos de um ASA, concebe e implementa uma ferramenta ASA voltada para o ensino-aprendizagem de cálculo proposicional, acompanhada de um plano de ensino opcional, e os coloca à disposição da comunidade acadêmica. Apresenta também estudos de casos sobre apresentações e usos da ferramenta em vários estágios de desenvolvimento, além da descrição de cada módulo e dos métodos e regras disponibilizados pela ferramenta. Pretende-se que a ferramenta ASA-CalcPro e o plano de ensino sugerido, sejam uma contribuição social positiva e um estímulo ao ensino-aprendizagem de cálculo proposicional. / The adequate use of computational environments can increase the quality and comfort of the teaching-learning process for some of the academic disciplines. A review of the literature reveals the lack of existing tools for the teaching-learning of the propositional calculus that conform to the criteria established for the student support environment (ambiente de suporte ao aluno (ASA)). As a consequence of this conclusion, the current thesis introduces the concept of, and the basic requirements for, an ASA, conceives and implements an ASA tool for the teaching-learning of the propositional calculus, together with an optional teaching plan, and puts both at the disposition of the academic community. The thesis also presents case studies of presentations and uses of the tool at various stages of its development, as well as a description of each module and of the methods and rules made available for use by the tool. It is hoped that the ASA-CalcPro tool and the suggested plan of study will make a positive social contribution and will be a stimulant for the teaching-learning of the propositional calculus.

This dissertation examines the syntax and semantics of clausal complements. It identifies semantic underpinnings for some syntactic properties of the arguments of propositional attitude verbs. The way clausal arguments compose with their embedding predicates is not uniform and semantic differences emerge from the syntactic context clausal arguments appear in. Three case studies are taken up: clausal arguments of nouns, dislocated clausal arguments (sentential subjects and topics), and infinitival complements with overt subjects (AcI constructions). Chapter Two assembles evidence to support Stowell’s (1981) claim that the clausal complements of nouns are modifiers. It is shown that the clausal complements of nouns behave like adjuncts in their ability to bleed condition C (Kuno 2004 and Jacobson 2003, and explored here further). The compositional strategy used to compose attitude nouns with their arguments, following Kratzer (2006), is shown to account for this behavior and to be commensurate with observations made by Grimshaw (1990). I then show how the modifier status of clausal complements of nouns is determined by the way in which nominals are formed from clause-taking verbs. Chapter Three examines another complementation strategy, found with fronted clauses. New data from binding is provided in support of Koster’s (1978) hypothesis that clauses do not move. Specifically, fronted clauses fail to show the effects of syntactic reconstruction. An analysis, making crucial use of de re attitude ascription, is offered to account for ‘apparent’ binding into fronted clauses. Chapter Four makes the case for enriching the meanings of clausal complements. By examining some new patterns with accusative with infinitive (AcI) constructions (such as I see him to be a fool), I argue for decomposing certain doxastic attitude verbs, putting the introduction of alternatives into the complement. Here too the role of de re attitude ascription is shown to play a crucial role. It is argued that AcI constructions involve de re attitude ascription, with added constraints (determined by the lexical content of the embedding verb) on the nature of the Acquaintance Relation (Kaplan 1968, Lewis 1979). Several predictions about the kinds of verbs that can participate in AcI are borne out.