Browsing Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Thèses et mémoires by Advisor "McKenzie, Pierre"
Now showing items 1-9 of 9
-
Algorithmique et complexité des systèmes à compteurs
(2016-09-28)L'un des aspects fondamentaux des systèmes informatiques modernes, et en particulier des systèmes critiques, est la possibilité d'exécuter plusieurs processus, partageant des ressources communes, de façon simultanée. De par leur nature concurrentielle, ... -
Automates à contraintes semilinéaires = Automata with a semilinear constraint
(2013-09-03)Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout ... -
Complexité raffinée du problème d'intersection d'automates
(2012-07-05)Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une ... -
The limits of Nečiporuk’s method and the power of programs over monoids taken from small varieties of finite monoids
(2019-03-13)Cette thèse porte sur des minorants pour des mesures de complexité liées à des sous-classes de la classe P de langages pouvant être décidés en temps polynomial par des machines de Turing. Nous considérons des modèles de calcul non uniformes tels que ... -
Le produit direct de fonctions et les programmes de branchement avec oracle
(2018-10-18)Ce mémoire explore divers résultats de la littérature à propos du produit direct de fonctions. Plus précisément, on retrouve la production de masse, le multi-calcul et l’espace catalytique. Le lien entre ces trois variantes du produit direct de ... -
Programmes de branchement catalytiques : algorithmes et applications
(2019-03-13)Le présent mémoire étudie le modèle de calcul des programmes de branchement k- catalytiques. Un programme de branchement k-catalytique sert à effectuer le calcul de k fonctions booléennes sur une même entrée et représente la contrepartie non uniforme ... -
Représentation d'un polynôme par un circuit arithmétique et chaînes additives
(2011-08-04)Un circuit arithmétique dont les entrées sont des entiers ou une variable x et dont les portes calculent la somme ou le produit représente un polynôme univarié. On assimile la complexité de représentation d'un polynôme par un circuit arithmétique au ...