We introduce abortable and query-abortable object types intended for implementation in asynchronous shared-memory systems with low contention. Implementations of such types behave like ordinary objects when accessed sequentially, but may abort operations when accessed concurrently. An aborted operation may or may not take effect, i.e., cause a state transition, and it returns no indication of which possibility occurred. Since this uncertainty can be problematic, a query-abortable type supports a QUERY operation that each process can use to determine its last non-QUERY operation on the object that caused a state transition, and the response associated with this state transition. Our research is closely related to obstruction-free implementations (introduced by Herlihy, Luchangco and Moir) and responsive obstruction-free implementations (introduced by Attiya, Guerraoui and Kouznetsov). Like abortable and query-abortable types, these implementations may exhibit degraded behaviour in the face of contention. We show that abortable registers--registers strictly weaker than safe registers--can be used to obtain obstruction-free and responsive obstruction-free implementations for any type. We present universal constructions for abortable and query-abortable types that are novel and efficient in the number of registers used. Specifically, they are based on a simple timestamping mechanism for detecting concurrent executions, and, in systems with n processes, use only n abortable registers or only O(n^2) single-reader, single-writer abortable registers. The timestamping mechanism we introduce is based on the inc&read counter type and appears to be interesting in its own right. As a generalization, we study the k-inc&read counter types, for k>0. We also identify a potential problem with correctness properties based on step contention: with such properties, the composition of correct object implementations may result in an implementation that is not correct. In other words, implementations defined in terms of step contention are not always composable. To avoid this problem, we introduce a property based on interval contention, namely non-triviality, to define the correct behaviour of abortable and query-abortable object implementations.

Les contraintes arithmétiques sont largement utilisées dans les langages formels comme les expressions, les grammaires d'arbres et les chemins réguliers. Ces contraintes sont utilisées dans les modéles de contenu des types (XML Schemas) pour imposer des bornes sur le nombre d'occurrences de nœuds. Dans les langages de requêtes (XPath, XQuery), ces contraintes permettent de sélectionner les nœuds ayant un nombre limité de nœuds accessibles par une expression de chemin donnée. Les types et chemins étendus avec les contraintes de comptage constituent le prolongement naturel de leurs homologues sans comptage déjà considérés comme des constructions fondamentales dans les langages de programmation et les systèmes de type pour XML. Un des défis majeurs en programmation XML consiste à développer des techniques automatisées permettant d'assurer statiquement un typage correct et des optimisations de programmes manipulant les données XML. À cette fin, il est nécessaire de résoudre certaines tâches de raisonnement qui impliquent des constructions telles que les types et les expressions XPath avec des contraintes de comptage. Dans un futur proche, les compilateurs de programmes XML devront résoudre des problèmes de base tels que le sous-typage afin de s'assurer au moment de la compilation qu'un programme ne pourra jamais générer de documents non valides à l'exécution. Cette thèse étudie les logiques capables d'exprimer des contraintes de comptage sur les structures d'arbres. Il a été montré récemment que le mu-calcul sur les graphes, lorsqu'il est étendu à des contraintes de comptage portant exclusivement sur les nœuds successeurs immédiats est indécidable. Dans cette thèse, nous montrons que, sur les arbres finis, la logique avec contraintes de comptage est décidable en temps exponentiel. En outre, cette logique fournit des opérateurs de comptage selon des chemins plus généraux. En effet, la logique peut exprimer des contraintes numériques sur le nombre de nœuds descendants ou même ascendants. Nous présentons également des traductions linéaires d'expressions XPath et de types XML comportant des contraintes de comptage dans la logique. / Arithmetical constraints are widely used in formal languages like regular expressions, tree grammars and paths. In XML they are used to impose bounds on the number of occurrences described by content models of schema languages (XML Schema, RelaxNG). In query languages (XPath, XQuery), they allow selecting nodes that have a bounded number of nodes reachable by a given path expression. Counting types and paths are thus natural extensions of their countless counterparts already regarded as the core constructs in XML languages and type systems. One of the biggest challenges in XML is to develop automated techniques for ensuring static-type safety and optimization techniques. To this end, there is a need to solve some basic reasoning tasks that involve constructions such as counting XML schemas and XPath expressions. Every compiler of XML programs will have to routinely solve problems such as type and path type- checking, for ensuring at compile time that invalid documents can never arise as the output of XML processing code. This thesis studies efficient reasoning frameworks able to express counting constraints on tree structures. It was recently shown that the mu-calculus, when extended with counting constraints on immediate successor nodes is undecid able over graphs. Here we show that, when interpreted over finite trees, the logic with counting constraints is decidable in single exponential time. Furthermore, this logic allows more general counting operators. For example, the logic can pose numerical constraints on number of ancestors or descendants. We also present linear translations of counting XPath expressions and XML schemas into the logic.

Tanto as incubadoras como as aceleradoras são organizações especializadas no suporte de empreendimentos em fases iniciais, em especial, aqueles intensivos em inovação conhecidos como startups. Apesar da grande disseminação dessas organizações, há poucas informações na literatura que evidenciem as suas diferenças e as contribuições na jornada do empreendedorismo inovador. Assim, o objetivo principal deste estudo é comparar a diferença entre as propostas de valor das aceleradoras e das incubadoras a partir da percepção das startups que tenham sido tanto incubadas como aceleradas. Entre os objetivos específicos temos: discutir possíveis relações entre as aceleradoras e as incubadoras de negócios; apresentar a evolução das incubadoras e os fatores que induziram o surgimento das aceleradoras, descrevendo os diferentes arquétipos e as implicações que essas organizações têm no ecossistema de empreendedorismo; apresentar o cenário nacional do fenômeno de aceleração e de incubação. O levantamento de dados contará com duas etapas: análise documental de fontes de dados secundárias e estudos de caso com uso de técnica de entrevista e questionário semiestruturado. A análise documental foi feita a partir de banco de dados de artigos científicos, dados oficiais de governos, fundações, revistas e páginas web especializadas e editais de chamamento das próprias organizações. A análise documental fornecerá o retrato de como as incubadoras e as aceleradoras se promovem no ecossistema como organizações importantes no apoio às startups. Em seguida, através de abordagem exploratória descritiva e qualitativa, foram realizadas entrevistas com roteiros semiestruturados com fundadores de startups que foram incubadas e aceleradas, para compreender o valor que cada um desses processos forneceu ao desenvolvimento dessas empresas. Concluiu-se que existe uma dissonância entre o valor percebido pelas startups e o que as incubadoras e as aceleradoras promovem. Também foi possível identificar que a busca por recursos pelas startups tende a não seguir um processo linear, capturando as melhores oportunidades que estejam disponíveis no momento. Por fim, esta pesquisa é um passo exploratório para trazer novas evidências do fenômeno das startups e dos diferentes instrumentos que as constroem. Sugerem-se encaminhamentos que possam preencher lacunas na literatura a respeito dos fenômenos citados, indicando a necessidade de estudos futuros que adensem o conhecimento desse fenômeno. / Both incubators and acelerators are specialized organizations to support early-stage ventures, especially innovation-intensive ones known as startups. Despite the great spread of these organizations, there is a few information in the literature that show their differences and contributions in the journey of innovative entrepreneurship. The main objective of this study is comparing the difference between value porposition of accelerators and incubators from the perception of startups that have been both incubated and accelerated. The specific objectives are: to discuss possible relationships between accelerators and incubators; to present the evolution of the incubators and the factors that led to the emergence of the accelerators, describing the different accelerators archetypes and the implications in entrepreneurship ecosystem; to present the national scenario of acceleration and incubation. The data collection stage had two stages: documentary analysis of secondary data sources; and the case study using interview technique through semi-structured questionnaire. The documentary analysis was made from a database of scientific articles, official data from governments, foundations, journals and specialized web pages and incubators and accelerators calls for proposals. Documentary analysis provided a picture of how incubators and accelerators are promoted to the ecosystem and startups. Then, through a descriptive and qualitative exploratory approach, interviews were conducted with semistructured scripts with founders of startups that were incubated and accelerated to understand the value that each of these processes provided to the development of these companies. It was concluded that there is a dissonance between what the incubators and the accelerators promote and the value perceived by the startups, they are not being able to identify enough characteristics that distinguish them. The reason for it is the diversity of the needs and demands of the startups, different models of accelerators and incubators are formulated that, in many cases, overlap in the benefits offered. It was also possible to identify that the search for resources by startups, whether radical or disruptive startups, does not follow a linear process, capturing the best opportunities available in the ecosystem through a minimally tactical and selective approach. In order to contribute to the understanding of the growing formation of organizations supporting startups, such as incubators and accelerators, and considering the findings of this research, a tool was suggested to define the types of these organizations, loosely termed \"startup guiders\". This tool analyzes three basic dimensions: business model, value proposition and stage of intervention in the development of early-stages ventures. Finally, this research is an exploratory step in bringing new evidence of the phenomenon of startups and of the different instruments that construct them. It is suggested that there be gaps in the literature regarding the mentioned phenomena, indicating the need for future studies that increase the knowledge of this phenomenon.

La production statuaire féminine de la fin de la République et du début de l’époque impériale se révèle être bien plus variée que ce que les anciennes études ont mis en évidence jusqu’à présent. La présente étude propose une critique des précédentes classifications typologiques à partir d’un corpus documentaire comprenant deux cent quatre statues en ronde bosse et haut-relief. L’étude de ce corpus a permis de mettre en lumière l’existence d’un riche répertoire de variantes aux types statuaires officiels et d’élaboration hellénistique. Ces variantes statuaires se révèlent être fondamentales pour la compréhension des relations entre les différentes régions de l’Empire ainsi que des traditions artisanales locales qui s’imposent encore parfois face à l’élaboration du langage de l’art augustéen. En même temps, l’analyse des statues féminines dans leur contexte a permis de démontrer une différence substantielle entre le plan de l’art officiel et celui de la production privée : contrairement aux choix iconographiques et stylistiques réservés aux hommes, les premières statues honorifiques des femmes romaines ne se révèlent pas totalement soumises aux règles de l’imitatio principis. L’importance de cette étude repose dans l’originalité de cette période de transition entre les modèles féminins issus de la précédente expérience iconographique hellénistique et ceux élaborés au cours de la période impériale romaine. / The statues of roman women during the end of the Republic and the first decades of the Empire were far more diversified than what previous scholars have claimed so far. Thanks to two-hundred and four female statues on round and high-reliefs collected from the west provinces of the roman Empire, the classifications proposed in the previous studies are retreated in order to stress the existence of a rich group of variations, which were different from the hellenistic statue types or from those which had been introduced during the imperial period. This variations are fundamental for the understanding of the relations between the different regions of the Empire as is the knowledge of traditional handicrafts, which were still heterogeneous in spite of the hellenization of roman art in the roman Republic. Moreover, this study of female honorific statues stresses the difference between the private and the official levels: on the contrary of masculine honorific sculpture, the first female statues from honorific context don't strictly reproduce the types and the facial features of female members of the Domus Augusta. The importance of this study resides in the peculiarity of this period of transition that, lying between the hellenistic and the imperial eras, represents a key moment for the elaboration of the image of the roman woman.

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

The use of databases for managing spatial data is widespread due to the efficiency of traditional SQL databases like Azure SQL. However, the exponential growth of data from sources like social media has led to the popularity of NoSQL databases such as MongoDB that handle large volumes of data effectively. NoSQL databases, including MongoDB, have built-in support for geospatial queries, making them suitable for managing geospatial data. Geospatial data combines geometric and geographic information and is represented by spatial datatypes like Point, LineString, and Polygon. MySQL and MongoDB both support geospatial data, but limited studies are comparing their performance in geospatial queries. An experiment was conducted to compare the fetch speed of geospatial data in these databases. The results were analyzed using graphs and related studies to draw conclusions, which showed that MongoDB performed slower fetch requests than MySQL. Future studies can use more data points and different queries.

No description available.

Homotopy Type Theory (HoTT) is a quite recent branch of research in mathematical logic, which provides interesting connections among various areas of mathematics. It was first introduced by Vladimir Voevodsky as a means to develop synthetic homotopy theory, and further advancements suggested that it can be used as a formal foundation to mathematics. Among its notable features, inductive and higher inductive types are of great interest, e.g. allowing for the study of geometric entities (such as spheres) in the setting of HoTT. However, so far in most of the literature higher inductive types are treated in an ad-hoc way; there is no easy general schema stating what an higher inductive type is, thus hindering the study of the related proof theory. Moreover, although Martin-Löf Type Theory has been deeply and widely studied, many proof theoretic results about its specific variant used in HoTT are folklore, and the proofs are missing. In this final talk, we provide an overview on some results we obtained, aiming to address these problems. In the first part of the talk, we will discuss a normalization theorem for the type theory underlying HoTT. In the second part of the talk we will propose a general syntax schema to encapsulate a relevant class of higher inductive types, potentially allowing for future study of the proof theory of HoTT enriched with such types.

Les structures avec des lieurs sont très communes en informatique. Les langages de programmation et les systèmes logiques sont des exemples de structures avec des lieurs. La manipulation de lieurs est délicate, de sorte que l’écriture de programmes qui ma- nipulent ces structures tirerait profit d’un soutien spécifique pour les lieurs. L’environ- nement de programmation Beluga est un exemple d’un tel système. Nous développons et présentons ici un compilateur pour ce système. Parmi les programmes pour lesquels Beluga est spécialement bien adapté, plusieurs peuvent bénéficier d’un compilateur. Par exemple, les programmes pour valider les types (les "type-checkers"), les compilateurs et les interpréteurs tirent profit du soutien spécifique des lieurs et des types dépendants présents dans le langage. Ils nécessitent tous également une exécution efficace, que l’on propose d’obtenir par le biais d’un compilateur. Le but de ce travail est de présenter un nouveau compilateur pour Beluga, qui emploie une représentation interne polyvalente et permet de partager du code entre plusieurs back-ends. Une contribution notable est la compilation du filtrage de Beluga, qui est particulièrement puissante dans ce langage. / In computer science, structures with variable binders are very common. Program- ming languages and logical frameworks are examples of structures with binders. Thus writing programs that deal with these kinds of data benefits with explicit support for data binding. The Beluga programming environment is an example of such a system. In this work we develop and present a compiler for the system. Many of the programs that Beluga is specially well suited for writing can benefit from a compiler. For example, some of the kinds programs that would benefit more are type-checkers, compilers and interpreters that take advantage of the binder support and dependent types present in the language, and also require a reasonably fast run-time. Our goal in this work, is to present a compiler for the Beluga system, that uses a very versatile internal representation that helps with the development of the system, and allows a sharing of code between several back-ends. Furthermore, we present a way of compiling the uniquely powerful pattern language supported by Beluga.

Pour fournir une disponibilité permanente des données et réduire la latence réseau, les systèmes de partage de données se basent sur la réplication optimiste. Dans ce paradigme, il existe plusieurs copies de l'objet partagé dite répliques stockées sur des sites. Ces répliques peuvent être modifiées librement et à tout moment. Les modifications sont exécutées en local puis propagées aux autres sites pour y être appliquées. Les algorithmes de réplication optimiste sont chargés de gérer les modifications parallèles. L'objectif de cette thèse est de proposer une méthodologie d'évaluation pour les algorithmes de réplication optimiste. Le contexte de notre étude est l'édition collaborative. Nous allons concevoir pour cela un outil d'évaluation qui intègre un mécanisme de génération de corpus et un simulateur d'édition collaborative. À travers cet outil, nous allons dérouler plusieurs expériences sur deux types de corpus: synchrone et asynchrone. Dans le cas d'une édition collaborative synchrone, nous évaluerons les performances des différents algorithmes de réplication sur différents critères tels que le temps d'exécution, l'occupation mémoire, la taille des messages, etc. Nous proposerons ensuite quelques améliorations. En plus, dans le cas d'une édition collaborative asynchrone, lorsque deux répliques se synchronisent, les conflits sont plus nombreux à apparaître. Le système peut bloquer la fusion des modifications jusqu'à ce que l'utilisateur résolut les conflits. Pour réduire le nombre de ces conflits et l'effort des utilisateurs, nous proposerons une métrique d'évaluation et nous évaluerons les différents algorithmes sur cette métrique. Nous analyserons le résultat pour comprendre le comportement des utilisateurs et nous proposerons ensuite des algorithmes pour résoudre les conflits les plus important et réduire ainsi l'effort des développeurs. Enfin, nous proposerons une nouvelle architecture hybride basée sur deux types d'algorithmes de réplication. Contrairement aux architectures actuelles, l'architecture proposéeest simple, limite les ressources sur les dispositifs clients et ne nécessite pas de consensus entre les centres de données / To provide a high availability from any where, at any time, with low latency, data is optimistically replicated. This model allows any replica to apply updates locally, while the operations are later sent to all the others. In this way, all replicas eventually apply all updates, possibly even in different order. Optimistic replication algorithms are responsible for managing the concurrent modifications and ensure the consistency of the shared object. In this thesis, we present an evaluation methodology for optimistic replication algorithms. The context of our study is collaborative editing. We designed a tool that implements our methodology. This tool integrates a mechanism to generate a corpus and a simulator to simulate sessions of collaborative editing. Through this tool, we made several experiments on two different corpus: synchronous and asynchronous. In synchronous collaboration, we evaluate the performance of optimistic replication algorithms following several criteria such as execution time, memory occupation, message's size, etc. After analysis, some improvements were proposed. In addition, in asynchronous collaboration, when replicas synchronize their modifications, more conflicts can appear in the document. In this case, the system cannot merge the modifications until a user resolves them. In order to reduce the conflicts and the user's effort, we propose an evaluation metric and we evaluate the different algorithms on this metric. Afterward, we analyze the quality of the merge to understand the behavior of the users and the collaboration cases that create conflicts. Then, we propose algorithms for resolving the most important conflicts, therefore reducing the user's effort. Finally, we propose a new architecture for supporting cloud-based collaborative editing system. This architecture is based on two optimistic replication algorithms. Unlike current architectures, the proposed one removes the problems of the centralization and consensus between data centers, is simple and accessible for any developers