7577 articles
Cet article établit que la vérification de module des systèmes multi-agents à pile (PMS) est 2EXPTIME-complète pour ATL, mais 4EXPTIME-complète pour ATL*, ce qui constitue un cas rare d'un problème de décision élémentaire dont la complexité dépasse le temps tri-exponentiel.
Cet article démontre que les compteurs probabilistes, tels que le compteur de Morris et le MaxGeo Counter, peuvent assurer la protection de la vie privée dans les agrégations de données sans ajout de randomisation externe, grâce à leur randomisation inhérente suffisante pour satisfaire les critères rigoureux de la confidentialité différentielle.
Cet article généralise l'opération de commutation sur les graphes , résout des problèmes ouverts concernant les homomorphismes et les produits catégoriels, et détermine le nombre chromatique pour les forêts en utilisant des notions de théorie des groupes.
Cette étude propose un cadre méthodologique combinant l'identification d'instances de demande excédentaire et un modèle de régression de Poisson filtré pour estimer la demande non satisfaite dans les systèmes de transport public, en appliquant cette approche aux données de la Port Authority de Pittsburgh pour corriger les biais liés aux données censurées.
Cette étude réexamine les biais implicites dans le arbitrage de la NBA en utilisant des données de jeu et des rapports des deux dernières minutes, révélant un avantage significatif pour les équipes à domicile (atténué depuis la pandémie) et des préférences individuelles pour certains joueurs, tout en ne trouvant aucune preuve de biais racial ou de défaveur envers des équipes ou des joueurs spécifiques.
Cet article présente un nouveau problème de sélection de plans de requêtes informatifs (TIPS) et un algorithme d'approximation associé pour aider les étudiants à mieux comprendre les choix de l'optimiseur de requêtes, dont l'efficacité est validée par des études pédagogiques sur trois ans.
Cet article présente une preuve élémentaire et nouvelle de la propriété de modèle fini pour l'algèbre de Kleene en utilisant des automates de transformation, établissant ainsi la complétude de cette théorie par rapport aux modèles relationnels finis et unifiant les résultats de Palka et Pratt.
Cet article étudie les mots de Dyck dans les séquences binaires, en démontrant que les mots sans puissances ont un niveau d'imbrication borné, en caractérisant explicitement les facteurs de Dyck du mot de Thue-Morse et en établissant des bornes serrées pour leur nombre.
Cet article réexamine un théorème classique sur les automates des représentations en utilisant le prouveur Walnut pour en obtenir une preuve computationnelle directe, permettant ainsi de démontrer de manière uniforme et automatique des résultats existants et d'en établir de nouveaux.
Cet article démontre que l'élimination d'un seul quantificateur universel dans les structures automatiques entraîne inévitablement une explosion doublement exponentielle de la complexité, rendant le problème de la vacuité EXPSPACE-complet et établissant de nouvelles bornes inférieures pour l'arithmétique de Büchi.
Cet article affine la technique des graphes de types pondérés pour prouver la terminaison des systèmes de transformation de graphes DPO, en augmentant leur puissance, en généralisant l'approche à d'autres catégories et en permettant des variations du formalisme DPO.
Cet article présente BOPIM, une méthode d'optimisation bayésienne conçue pour résoudre le problème de maximisation de l'influence sur des réseaux temporels en surmontant les défis liés à l'espace combinatoire via des noyaux adaptés et une fonction d'acquisition optimisée, offrant ainsi des performances supérieures en vitesse et en précision par rapport aux méthodes existantes tout en permettant pour la première fois de quantifier l'incertitude des ensembles de nœuds sémences optimaux.
Cette étude longitudinale révèle que les mises à jour successives des grands modèles de langage (GPT, Llama, Qwen) n'améliorent pas systématiquement leur robustesse face aux exemples adverses (erreurs de classification, jailbreaks et hallucinations), montrant parfois même une dégradation des performances malgré des améliorations ciblées.
Cet article généralise les axiomes de cardinalité des algèbres de relations aux algèbres de Stone pour modéliser les graphes pondérés, propose des axiomes simplifiés et établit des conditions suffisantes pour la représentabilité de ces structures.
Cet article établit une caractérisation des ensembles de graphes à la fois définissables en logique monadique du second ordre avec comptage et contextuels, en démontrant leur équivalence avec des ensembles reconnaissables de largeur arborescente bornée, des ensembles parsables et des images de transductions définissables d'arbres non rangés, grâce à une connexion novatrice entre les résultats de Courcelle et Engelfriet et ceux de Bojanczyk et Pilipczuk.
Cet article démontre que l'ajout de la règle d'échange réduit considérablement le nombre de variétés de treillis résiduels idempotents et semi-linéaires possédant la propriété d'amalgamation, passant d'une infinité continue pour les logiques non commutatives à exactement soixante pour les logiques commutatives.
Cet article établit une fondation pour un calcul des expressions de langages contextuels sans lieurs de variables en exploitant une représentation par automates et des formes normales au sein d'un produit tensoriel d'algèbres de Kleene, tout en analysant les propriétés des algèbres polycycliques et .
Cet article présente un algorithme en temps polynomial pour partitionner un polygone simple en un nombre minimal de polygones en forme d'étoile, résolvant ainsi un problème théorique ouvert depuis plus de quarante ans.
Cet article généralise les inégalités relatives à la fonction sommatoire de la somme des chiffres en base donnée et démontre que plusieurs résultats connus découlent d'un théorème publié en 2023 par Mohanty et ses collègues, initialement consacré à la robustesse mutationnelle maximale dans les cartes génotype-phénotype.
Les auteurs démontrent que le problème d'isomorphisme pour les tournois de largeur jumeau bornée est décidable en temps polynomial, en utilisant des techniques de théorie des groupes, et établissent que cette propriété ne s'applique pas aux graphes non orientés ni aux algorithmes de Weisfeiler-Leman de dimension sous-linéaire.