Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

The theory of moral sentiments; or, an essay towards an analysis of the principles by wich men naturally judge concerning the conduct and character, first of their neighbours, and afterwards of themselves : to which is added a dissertation on the origin of languages

by Adam Smith, LL.D., fellow of the royal societies of London and Edinburgh, one of the commissioners of his majesty's customs in Scotland, and formerly professor of moral philosophy in the University of Glasgow

Topologies on groups related to the theory of shape and generalized coverings

El presente trabajo consiste en dos partes diferenciadas: la principal de ellas (Cap tulos 1 y 2) est a dedicada a introducir estructura adicional en grupos que aparecen de manera natural en el contexto de la teor a de la forma. En la segunda parte (Cap tulo 3), se plantea c omo generalizar la teor a de espacios recubridores y, en particular, se propone una l nea de trabajo relacionada con la teor a de la forma. El punto de partida de esta tesis doctoral son los trabajos [25, 26, 68, 69, 70] en los que los autores introducen y utilizan algunas ultram etricas en el conjunto de los mor smos shape entre dos espacios topol ogicos punteados. En particular, si el dominio es (S1; 1); la construcci on realizada en [68] permite explicitar una ultram etrica en el grupo shape 1(X; x0) de un espacio m etrico compacto X; como ya fue observado en [69] y [80]. Si el espacio no es m etrico compacto, la construcci on nos lleva a utilizar el concepto de ultram etrica generalizada, en el sentido de Priess-Crampe y Ribenboim [78, 79]. En [7], D. K. Biss introduce la idea de topologizar el grupo fundamental de un espacio, de forma que la topolog a en 1(X; x0) sea una topolog a de grupo que permita detectar la (no) existencia de un recubridor universal para X: La forma de proceder sugerida es tomar en 1(X; x0)la toplog a cociente inducida por la topolog a compacto-abierta en el espacio de lazos (X; x0): Sin embargo, hay algunos errores en el art culo mencionado: en concreto, el error relacionado con el presente trabajo fue puesto de mani esto por P. Fabel en [33], mostrando que, en general, la operaci on de grupo en 1(X; x0)con la topolog a cociente no es continua. Utilizando un punto de vista similar, varios autores han tratado de dotar al grupo fundamental con una topolog a, de forma que 1(X; x0) sea un grupo topol ogico y la proyecci on q (X; x0){u100000} 1(X; x0)sea continua...

Notes on the Floridian Theory of Strongly Semantic Information

Other

Ontology and gnoseology of capitalism in Isaak Illich Rubin: 'Essays on marxist theory of value'

This concise essay attempts to show why Isaak Illich Rubin is, until today, the best interpreter, commentator and developer of The Capital of Karl Marx, understanding Marx’s work as an ontology and a gnoseology of the capitalist economic system. To do this, we analyze the relations existing between Marx, Rubin and the theory of science of the Spanish Marxist philosopher Gustavo Bueno. In this way, we can interpret the work “Essays on Marxist theory of value” also as an ontology and a gnoseology of capitalism.

Bimodal adaptive hypermedia and interactive multimedia a web-based learning environment based on Kolb's theory of learning style

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

A critical theory of rhythm and temporality in film : the metamorphosis of memory and history in Tarkovsky's Mirror (1975)

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.