Usages des structures algébriques en informatique théorique

Je suis un praticien en logiciel et j'écris une étude sur les structures algébriques à des fins de recherche personnelle et j'essaie de produire des exemples d'utilisation de ces structures en informatique théorique (et, dans une moindre mesure, dans d'autres sous-domaines de l'informatique). .

Sous la théorie des groupes, j'ai rencontré des monoïdes syntaxiques pour les langages formels et des monoïdes de trace et d'historique pour l'informatique parallèle / simultanée.

Du point de vue de la théorie des anneaux, je suis tombé sur des cadres de semiring pour le traitement de graphes et l’analyse basée sur le semiring.

Je n'ai pas encore trouvé d'utilisation de structures algébriques à partir de la théorie des modules dans mes recherches (et j'aimerais le faire).

Je suppose qu'il existe d'autres exemples et que je ne cherche tout simplement pas le bon endroit pour les trouver.

Quels sont d'autres exemples de structures algébriques des domaines énumérés ci-dessus que l'on trouve couramment en informatique théorique (et dans d'autres sous-domaines de l'informatique)? Sinon, quelles revues ou autres ressources pouvez-vous recommander qui pourraient couvrir ces sujets?

Mon impression est que, dans l'ensemble, l'algèbre traditionnelle est un peu trop spécifique pour être utilisée en informatique. Les informaticiens utilisent donc soit des structures plus faibles (et donc plus générales), soit généralisent les structures traditionnelles afin de les adapter à leurs besoins. Nous utilisons également beaucoup la théorie des catégories, que les mathématiciens ne considèrent pas comme faisant partie de l’algèbre, mais nous ne voyons pas pourquoi. Nous trouvons que la réglementation des mathématiques traditionnelles en "algèbre" et en "topologie" comme des branches séparées est gênante, voire inutile, car l'algèbre est généralement du premier ordre alors que la topologie a une chance de traiter des aspects d'ordre supérieur. Ainsi, les structures utilisées en informatique ont une algèbre et une topologie mélangées. En fait, je dirais qu'elles tendent davantage vers la topologie que l'algèbre. L'intégration du raisonnement en "algèbre" et en "logique" est une autre division inutile de notre point de vue, car l'algèbre traite des propriétés équationnelles alors que la logique traite également de tous les autres types de propriétés.

Pour revenir à votre question, les semi-groupes et les monoïdes sont utilisés assez intensément dans la théorie des automates. Eilenberg a écrit une collection en deux volumes , dont le second est presque entièrement en algèbre. On me dit qu'il prévoyait quatre volumes mais son âge ne permettait pas de terminer le projet. Jean-Eric Pin dispose d'une version modernisée d'une grande partie de ce contenu dans un livre en ligne . Les automates sont des "modules monoïdes" (également appelés actions monoïdes ou "actes"), qui se situent au bon niveau de généralité en informatique. Les modules en anneau traditionnels sont probablement trop spécifiques.

La théorie du réseau était une force majeure dans le développement de la sémantique dénotationnelle. La topologie a été mélangée à la théorie du réseau lorsque des informaticiens, conjointement avec des mathématiciens, ont développé des réseaux continus puis les ont généralisés à des domaines . Je dirais que la théorie des domaines est la propre mathématique de l'informaticien, à laquelle les mathématiques traditionnelles n'ont aucune connaissance.

L'algèbre universelle est utilisée pour définir les spécifications algébriques des types de données . Une fois arrivés là-bas, les informaticiens ont immédiatement constaté la nécessité de traiter des propriétés plus générales: les équations conditionnelles (également appelées clauses de Horn équationnelles) et les propriétés logiques du premier ordre, en utilisant toujours les mêmes idées d’algèbre universelle. Comme vous le remarquerez, l'algèbre se fond maintenant dans la théorie des modèles.

La théorie des catégories est la base de la théorie des types. Alors que les informaticiens inventent sans cesse de nouvelles structures pour traiter divers phénomènes informatiques, la théorie des catégories est un cadre très réconfortant dans lequel placer toutes ces idées. Nous utilisons également des structures activées par la théorie des catégories, qui n'existent pas dans les mathématiques "traditionnelles", telles que les catégories de foncteurs. En outre, l'algèbre revient dans l'image d'un point de vue catégorique sur l'utilisation des monades et des théories algébriques des effets . Les coalgebras , qui sont les duals des algèbres, trouvent également beaucoup d'applications.

Ainsi, il existe une vaste application de "l'algèbre" en informatique, mais ce n'est pas le genre d'algèbre que l'on trouve dans les manuels d'algèbre traditionnels.

Note complémentaire : Il existe un sens concret dans lequel la théorie des catégories est algèbre. Le monoïde est une structure fondamentale en algèbre. Il consiste en un opérateur de "multiplication" binaire, associatif et ayant une identité. La théorie des catégories généralise ce en associant « types » aux éléments du monoïde, . Vous pouvez "multiplier" les éléments que lorsque les types correspondent: si un : X → Y et b : Y → Z puis un b : X → Z . Par exemple, n × $a : X \rightarrow Y$$a : X \rightarrow Y$$b : Y \to Z$$ab : X \to Z$$n \times n$les matrices ont une opération de multiplication qui en fait un monoïde. Cependant, les matrices (où m et n peuvent être différents) forment une catégorie. Les monoïdes sont donc des cas particuliers de catégories qui ont un seul type. Les anneaux sont des cas spéciaux de catégories additives qui ont un seul type. Les modules sont des cas spéciaux de foncteurs où les catégories source et cible ont un type unique. Bientôt. La théorie des catégories est une algèbre typée dont les types la rendent infiniment plus applicable que l'algèbre traditionnelle.$m \times n$$m$$n$

Mon application préférée de la théorie des groupes dans TCS est le théorème de Barrington. Vous pouvez trouver une exposition de ce théorème sur le blog de la complexité et l'exposition de Barrington dans la section commentaires de cet article.

Les groupes, les anneaux, les champs et les modules sont omniprésents dans la topologie informatique. Voir en particulier le travail [ex: 1 ] de Carlsson et Zomorodian sur l'homologie persistante (multidimensionnelle), qui consiste à définir des modules gradués sur des domaines idéaux principaux.

Voici une très belle utilisation pratique: un algorithme de calcul de la connectivité graphique (tiré de FOCS2011 ). Pour calculer la connectivité s-> t d'un graphe, les auteurs proposent un algorithme qui assigne des vecteurs aléatoires avec des entrées tirées d'un champ fini aux arêtes de s, puis construit des vecteurs similaires pour toutes les arêtes du graphe en prenant des variables aléatoires. combinaisons linéaires, et enfin découvrir la connectivité en calculant le rang des vecteurs résultants assignés aux bords de t.

Les treillis et les points fixes sont à la base de l'analyse et de la vérification de programmes. Bien que les résultats avancés de la théorie du réseau soient rarement utilisés car nous nous intéressons à des problèmes d’algorithme tels que l’informatique et l’approximation de points fixes, la recherche sur la théorie du réseau a un objectif différent (connexions à la topologie, théorie de la dualité, etc.). Les premiers documents d’interprétation abstraite utilisent la théorie de base du réseau. Le travail de Roberto Giacobazzi et de ses collaborateurs utilise des résultats plus avancés.

En informatique distribuée, une famille célèbre de résultats d'impossibilité a été dérivée en utilisant des méthodes de topologie algébrique (Voir le travail de Maurice Herlihy et Nir Shavit).

[Edit: Voir Applications de la topologie à l'informatique .]

L'algèbre universelle est un outil important pour étudier la complexité des problèmes de satisfaction de contraintes.

Par exemple, la conjecture de dichotomie indique que, grosso modo, un problème de satisfaction de contrainte sur un domaine fini est soit NP-complet, soit résolvable en temps polynomial. Notez que, selon le théorème de Ladner, il existe des problèmes dans NP qui ne sont ni dans P, ni dans NP-complet, à moins que P = NP, de sorte que la conjecture dit que les CSP ont la particularité d'avoir une dichotomie que ne possèdent pas les classes de complexité plus grandes. Cela expliquerait également pourquoi la plupart des problèmes que nous rencontrons dans la pratique peuvent être classés en NP-complet ou en P.

Les dichotomies ont été prouvées dans plusieurs cas particuliers, par exemple les CSP du domaine binaire (Schaefer) et les CSP du domaine ternaire (Bulatov), ​​et les homomorphismes en graphes non dirigés (Hell et Nesetril). Mais le cas général est assez ouvert. L'une des principales lignes d'attaque est l'algèbre universelle. Très grossièrement (et je ne suis certainement pas un expert en cela!), On définit un polymorphisme de CSP comme une fonction du domaine du CSP qui laisse toutes les contraintes satisfaites satisfaites s’il est appliqué à chaque variable. L'ensemble des polymorphismes d'un CSP en capture en quelque sorte la complexité. Par exemple, si un CSP A admet tous les polymorphismes d'un CSP B, alors A est un temps polynomial réductible à B. L'ensemble des polymorphismes forme une algèbre, dont la structure semble utile pour concevoir des algorithmes / montrer des réductions. Par exemple, si l'algèbre de polymorphisme d'un CSP est idempotente et admet le type unaire, alors le CSP est NP-complet. L'idempotence est une hypothèse simplificatrice qui peut être faite plus ou moins sans perte de généralité. Montrer qu'un CSP dont l'algèbre est idempotente et n'admet pas le type unaire peut être résolu en temps polynomial prouvera la conjecture de dichotomie.

Voir l'enquête de Bulatov: http://www.springerlink.com/content/a553847g6h673k05/ .

Voici deux applications d'une partie différente de TCS.

Les semirings sont utilisés pour modéliser les annotations dans les bases de données (en particulier celles nécessaires pour la provenance), et souvent aussi pour les structures d'évaluation dans la satisfaction des contraintes valorisées. Dans ces deux applications, les valeurs individuelles doivent être combinées ensemble de manière à aboutir naturellement à une structure de semiring, avec une associativité et une opération de semiring réparties sur l’autre. En ce qui concerne votre requête sur les modules, aucun des deux monoïdes n’a un inverse dans ces applications, en général.

• Todd J. Green, Grigoris Karvounarakis et Val Tannen. Semirings Provenance , PODS 2007. doi: 10.1145 / 1265530.1265535 ( pré-impression )
• Stefano Bistarelli, Ugo Montanari et Francesca Rossi. Satisfaction et optimisation des contraintes basées sur le semiring, JACM 1997. doi: 10.1145 / 256303.256306 ( preprint )

Les anneaux, les modules et les variétés algébriques sont utilisés dans la correction des erreurs et, plus généralement, dans la théorie du codage.

Plus précisément, il existe un schéma de correction d'erreur abstrait (codes de géométrie algébrique) qui généralise les codes de Reed-Solomon et les codes du reste chinois. Le système consiste essentiellement à prendre vos messages comme provenant d'un anneau R et à les encoder en prenant ses résidus modulo dans R différents idéaux différents. Sous certaines hypothèses sur R, on peut prouver que cela constitue un code correct de correction d'erreur.

Dans le monde du décodage par liste, un article récent de Guruswami décrit une méthode linéaire-algébrique de décodage par liste de codes de Reed-Solomon pliés, qui présente la propriété intéressante que tous les messages candidats se trouvent dans un sous-espace affine de dimension réduite de l'espace de message. . On peut construire des ensembles évasifs de sous-espace , des ensembles qui sont presque aussi grands que l’espace tout entier, mais ont une petite intersection avec chaque sous-espace affine de faible dimension. Si l'on restreint les messages provenant d'un ensemble évasif de sous-espace à l'intérieur de l'espace de message, le schéma de Guruswami fournit un algorithme garantissant la taille de la liste. Jusqu'à présent, Dvir et Lovett ont donné la seule construction explicite d'ensembles évasifs de sous-espace dans leur prochain article du STOC, Ensembles évasifs de sous-espace et construisez l’ensemble en prenant une variété affine spécifique (et en prenant son produit cartésien avec lui-même).

Découvrez la théorie de Ramsey - fondamentalement, une généralisation significative du principe du casier qui est à la base de beaucoup d’automates et de la théorie du langage formel (ou devrais-je dire, le principe du casier est le cas le plus simple de la théorie de Ramsey). Il dit fondamentalement que même les structures très désordonnées s'avèrent nécessairement contenir beaucoup d'ordre si elles sont suffisamment grandes. Pour un petit exemple juste au-delà du principe de casier, notez que si vous prenez six personnes, alors trois d’entre elles se connaissent ou trois ne se connaissent pas.

Ce document semble être un bon point de départ pour établir des liens avec l’informatique, mais vous pouvez en rechercher davantage sur Google. Il est plus combinatoire qu'algébrique dans sa nature fondamentale, mais a de nombreuses applications en algèbre et en CS théorique.

Découvrez également l'histoire de l'inventeur, Frank Ramsey - un polymathe remarquable qui a apporté des contributions fondamentales, voire révolutionnaires en économie et en philosophie, ainsi que des mathématiques, dont beaucoup n'ont été appréciées que beaucoup plus tard, avant de mourir à l'âge de 26 ans - il suffit de penser! En fait, le théorème original de Ramsey, la base de la théorie de Ramsey, était un simple lemme dans un article ayant un objectif plus vaste en logique mathématique.

L'utilisation de la théorie des groupes facilite l'analyse de tout problème présentant beaucoup de symétrie. Un exemple serait de trouver des algorithmes pour des choses comme le cube de rubic. Bien que je ne connaisse pas les détails, je suis sûr que prouver que le nombre de Dieu est 20 nécessite une taille théorique sérieuse en groupe. Dans un contexte différent, les solveurs pratiques pour le problème d'isomorphisme de graphe, tel que Nauty, utilisent le groupe d'automorphisme du graphe.

$\mathbb{Z}_p$

En programmation fonctionnelle, les abstractions de problèmes les plus générales et les plus élégantes sont souvent de nature algébrique (ou de catégorie théorique): monoïdes, semirings , foncteurs, monades, algèbres F , coalgebras F, etc. Quelques résultats classiques (par exemple, le Yoneda Lemma) ont un contenu et une utilité calculatoires.

Il existe également la théorie des types d'homotopie, qui interprète la théorie des types dans un cadre topologique algébrique (en quelque sorte).

Récemment, nous explorons (voir notre article sur springerlink: une unification formelle en série des approches d’extraction d’ensemble d’articles fréquents ) une tentative d’unification pour modeler des approches (une instance populaire d’extraction de données) au moyen de séries formelles et d’automates pondérés. Ces outils sont basés sur des mappages entre des monoïdes et des structures de semiring.