Techn. University, Diss., 2003--Berlin.

Universiẗat, Diss., 1993--Saarbrücken.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2017. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2017-04-26T14:09:10Z No. of bitstreams: 1 2017_ThiagoMendonçaFerreiraRamos.pdf: 615472 bytes, checksum: 07c6f1995d15d71ca3dce6b9186c1bb8 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2017-04-27T22:18:25Z (GMT) No. of bitstreams: 1 2017_ThiagoMendonçaFerreiraRamos.pdf: 615472 bytes, checksum: 07c6f1995d15d71ca3dce6b9186c1bb8 (MD5) / Made available in DSpace on 2017-04-27T22:18:25Z (GMT). No. of bitstreams: 1 2017_ThiagoMendonçaFerreiraRamos.pdf: 615472 bytes, checksum: 07c6f1995d15d71ca3dce6b9186c1bb8 (MD5) / Terminação é uma propriedade crítica para formalização de correção de programas. Verificar automaticamente terminação de um programa é conhecido como Problema da Parada e Turing provou que é um problema indecidível. Apesar disso, é possível construir algoritmos de semi decisão para verificar terminação, que respondem ‘sim’ se pode provar que o algoritmo para e ‘não sei’ caso contrário. Para construir esses algoritmos de semi decisão é necessário considerar diferentes noções de terminação, provando que são equivalentes. Neste trabalho, noções de terminação são formalizadas equivalentes para uma linguagem funcional de primeira ordem chamada PVS0 usando o assistente de prova Prototype Verification System. Essas noções são: as funções produzem uma saída, a árvore de derivação de chamados recursivos de funções tem tamanho finito (ambas as noções são chamadas terminação semântica), e os argumentos das funções decrescem para cada chamado recursivo (essa noção é chamada ranking function). As contribuições desse trabalho incluem a formalização de alguns lemas necessários para demonstrar equivalência entre noções de terminação semântica e ranking function, e como resultado principal a formalizações de indecidibilidade do Problema da Parada e Turing-Completude de PVS0. / Termination is a critical property for the formalization of programs correctness. Verifing automatically termination of a program for an input is known as Halting Problem and Turing proved that this is undecidable. However, it is possible to build semi decision algorithms for the verification of termination, that answer ‘yes’ if it is possible to prove that the algorithm halts, and ‘do not know’ otherwise. To construct these semi decision algorithms it is necessary to consider different notions of termination, proving that they are equivalent. In this work, notions of termination were formalized equivalent for a minimal functional first order language called PVS0 using the proof assistant Prototype Verification System. These notions are: the functions produces an output, the derivation tree of recursive calls of functions has a finite size (both these notions are called semantic termination), and the arguments of functions decreases for each recursive call (this notion is called ranking function). The contributions of this work includes formalization of lemma related with the equivalence between notions of semantic and ranking function termination, and the main results are the formalization of indecidability of Halting Problem and Turing-Completeness of PVS0.

Made available in DSpace on 2014-06-12T16:00:10Z (GMT). No. of bitstreams: 2 arquivo6087_1.pdf: 1872863 bytes, checksum: 5421c048c3358bc43e4f5ae9a04428fc (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Spam é o termo usado para referir-se aos e-mails não solicitados, que geralmente são enviados para um grande número de pessoas, e é hoje considerado um dos maiores problemas enfrentados na Internet. Com o aumento da disponibilização de banda larga, popularização de tecnologias de internet e o aumento da utilização e disponibilização de soluções baseadas em VoIP (Voice over IP), é esperado que um problema semelhante passe a afetar esta nova área. Esta ameaça é conhecida por SPIT (SPAM over Internet Telephony) e é definida como geração automatizada de chamadas não solicitadas utilizando como transporte o IP através do VoIP ao invés das tradicionais linhas telefônicas. O potencial do SPIT em reduzir a produtividade é muito maior do que a do SPAM, porque no SPIT a utilização de tempo de uma pessoa já é contabilizada a partir do momento em que o telefone começa a tocar. Podemos acrescentar que o SPIT não consiste apenas no incômodo a um usuário, quando aplicado contra uma rede, pois pode consumir seus recursos dificultando ou ainda inviabilizar a utilização dos recursos da rede. As características do SPIT são diferentes do SPAM, portanto não podemos aplicar as mesmas técnicas usadas no SPAM em ataques do tipo SPIT. Propomos neste trabalho uma ferramenta para identificar e proteger uma rede VoIP contra ataques de SPIT. Como visto em outros tipos de ameaças a redes de dados, a utilização de um único método não é suficiente para garantir a proteção e identificação dos ataques. Portanto, na nossa abordagem, a ferramenta desenvolvida faz uso de Testes Reversos de Turing formatados em um CAPTCHA no formato de uma mensagem de áudio, com o objetivo de identificar se a chamada é ou não um SPIT. Essa técnica é aplicada em conjunto com outras técnicas descritas ao longo do texto. Desta forma, é composta uma ferramenta de prevenção e identificação com a finalidade de garantir uma melhor proteção contra ataques de SPIT, em redes baseadas em VoIP

<p> The notion of nondeterminism is one of the most fundamental concepts in many areas of computer science. Unambiguity, requiring that there be at most one correct sequence of nondeterministic choices, has proved to be one of the most meaningful restrictions of nondeterminism. In the context of space-bounded Turing Machines, several variants of unambiguity have been proposed and studied, and some interesting results have been established, narrowing slightly the gap between deterministic and nondeterministic logarithmic-space computation.</p> <p> We study the different variants of unambiguity in the context of computing multi-valued functions (as opposed to the usual yes/no decision problems). We propose a modification to the standard computation models of Turing Machines and configuration graphs, which allows for unambiguity-preserving composition. We introduce a unified notation, capturing the different flavors of ambiguity. Furthermore, we define a notion of reductions (based on function composition), which allows non-determinism but controls its level of ambiguity. In the light of this framework we establish some reductions between different variants of path counting problems. We also investigate more carefully the technique of inductive counting, and obtain improvement of some existing results.</p> / Thesis / Doctor of Philosophy (PhD)

La presente investigación evalúa el concepto de computabilidad en la teoría de Alan Turing, justificándose por la existencia de opiniones divergentes entre diversos académicos, expresadas alrededor del significado de la tesis de Church-Turing, que trata a la función recursiva como equivalente al procedimiento efectivo. En la actualidad, operamos computadoras conectadas a la Internet, resultando habitual relacionar como computabilidad lo que se puede hacer en una computadora. Muy pocas veces asociamos a la computadora con la ejecución de un cálculo aritmético, tal vez porque disponemos de las máquinas calculadoras. En un sentido amplio, utilizamos la palabra computable como sinónimo de la obtención de un resultado utilizando una computadora. Cuando mencionamos cálculos, no sólo significa operaciones numéricas, también corresponde a operar símbolos, como ocurre cuando entendemos los elementos que nos rodean, los percibimos como fenómenos, incluso nos percatamos del ánimo de las personas y las interpretamos, aunque no siempre acertemos sobre los estados de ánimo.

This report discusses simulators in automata theory and which one should be best for use in laboratory assignments. Currently, the Formal Languages, Automata and Theory of Computation course (FABER) at Mälardalen University uses the JFLAP simulator for extra exercises. To see if any other simulators would be useful either along with JFLAP or standalone, tests were made with nine programs that are able to graphically simulate automata and formal languages. This thesis work started by making an overview of simulators currently available.After the reviews it has become clear to the author that JFLAP is the best choice for majority of cases. JFLAP is also the most popular simulator in automata theory courses worldwide.To support the use of JFLAP for the course a manual and course assignments are created to help the student to getting started with JFLAP. The assignments are expected to replace the current material in the FABER course and to help the uninitiated user to get more out of JFLAP.

Thesis (Ph. D.)--University of Washington, 1998. / Vita. Includes bibliographical references (p. [155]-167).

Master of Science / Department of Computer Science / Torben Amtoft / Shannon’s and Chomsky’s attempts to model natural language with Markov chains showed differing gauges of language complexity. These were codified with the Chomsky Hierarchy with four types of languages, each with an accepting type of grammar and au- tomaton. Though still foundationally important, this fails to identify remarkable proper subsets of the types including recursive languages among recursively enumerable languages. In general, with Rice’s theorem, it is undecidable whether a Turing machine’s language is re- cursive. But specifically, Hopcroft & Ullman show that the languages of space bound Turing machines are recursive. We show the converse also to be true. The space hierarchy theorem shows that there is a continuum of proper subsets within the recursive languages. With Myhill’s description of a linear bounded automata, Landweber showed that they accept a subset of the type 1 languages including the type 2 languages. Kuroda expanded the definition making the automata nondeterministic and showed that nondeterministic linear space is the set of type 1 languages. That only one direction was proven deterministically but both nondeterministically, would suggest that nondeterminism increases expressiveness. This is further supported by Savitch’s theorem. However, it is not without precedent for predictions in computability theory to be wrong. Turing showed that Hilbert’s Entschei- dungsproblem is unsolvable and Immerman disproved Landweber’s belief that type 1 lan- guages are not closed under complementation. Currently, a major use of language theory is computer language processing including compilation. We will show that for the Java programming language, compilability can be computed in nondeterministic linear space by the existence of a (nondeterministic) linear bounded automaton which abstractly computes compilability. The automaton uses the tra- ditional pipeline architecture to transform the input in phases. The devised compiler will attempt to build a parse tree and then check its semantic properties. The first two phases, lexical and syntactical analysis are classic language theory tasks. Lexical analysis greedily finds matches to a regular language. Each match is converted to a token and printed to the next stream. With this, linearity is preserved. With a Lisp format, a parse tree can be stored as a character string which is still linear. Since the tree string preserves structural information from the program source, the tree itself serves as a symbol table, which normally would be separately stored in a readable efficient manner. Though more difficult than the previous step, this will also be shown to be linear. Lastly, semantic analysis, including typechecking, and reachability are performed by traversing the tree and annotating nodes. This implies that there must exist a context-sensitive grammar that accepts compilable Java. Therefore even though the execution of Java programs is Turing complete, their compilation is not.

Submitted by JOÃO PAULO DA CRUZ ALMEIDA (joaopauloalmeida2010@gmail.com) on 2017-09-26T16:20:50Z No. of bitstreams: 1 Minha Dissertação.pdf: 1021011 bytes, checksum: 1717c0a1baae32699bdf06c781a9ed31 (MD5) / Approved for entry into archive by Monique Sasaki (sayumi_sasaki@hotmail.com) on 2017-09-28T12:58:50Z (GMT) No. of bitstreams: 1 almeida_jpc_me_sjrp.pdf: 1021011 bytes, checksum: 1717c0a1baae32699bdf06c781a9ed31 (MD5) / Made available in DSpace on 2017-09-28T12:58:50Z (GMT). No. of bitstreams: 1 almeida_jpc_me_sjrp.pdf: 1021011 bytes, checksum: 1717c0a1baae32699bdf06c781a9ed31 (MD5) Previous issue date: 2017-06-29 / Este trabalho apresenta uma proposta relacionada ao ensino e prática do pensamento dedutivo formal em Matemática. São apresentados no âmbito do conjunto dos números Naturais três temas essencialmente interligados: indução/boa ordem, dedução e esquemas de computação representados pela máquina teórica de Turing. Os três temas se amalgamam na teoria lógica de dedução e tangem os fundamentos da Matemática, sua própria indecidibilidade e extensões / limites de tudo que pode ser deduzido utilizando a lógica de Aristóteles, caminho tão profundamente utilizado nos trabalhos de Gödel, Church, Turing, Robinson e outros. São apresentadas inúmeros esquemas de dedução referentes às “fórmulas” e Teoremas que permeiam o ensino fundamental e básico, com uma linguagem apropriada visando treinar os alunos (e professores) para um enfoque mais próprio pertinente à Matemática. / This work deals with the teaching and practice of formal deductive thinking in Mathematics. Three essentially interconnected themes are presented within the set of Natural Numbers: induction, deduction and computation schemes represented by the Turing theoretical machine. The three themes are put together into the logical theory of deduction and touch upon the foundations of Mathematics, its own undecidability and the extent / limits of what can be deduced by using Aristotle's logic, that is the subject in the works of Gödel, Church, Turing, Robinson, and others. There are a large number of deduction schemes referring to the "formulas" and Theorems that are usual subjects in elementary and basic degrees of the educational field, with an appropriate language in order to train students (and teachers) for a more pertinent approach to Mathematics.