4485 articles
Cet article étudie les mots de Dyck dans les séquences binaires, en démontrant que les mots sans puissances $7/3$ 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.
Ce papier propose une approche de réécriture symbolique pour composer des propriétés LTL sur des composants logiciels asynchrones interagissant via des ports de données, en traitant à la fois les traces infinies et finies, et en intégrant cette méthode dans l'outil OCRA pour valider sa pertinence par rapport aux approches existantes.
Cet article établit une preuve simple reliant deux types de récurrences de Fibonacci -aires au dénombrement de mots -régulaires évitant certains motifs, complète ce résultat par un nouveau théorème pour une autre classe de motifs, et émet une conjecture sur les nombres de Fibonacci au carré dans le contexte des motifs vinculaires.
Cet article caractérise complètement les langages ω-réguliers positionnels via les automates de parité, établissant ainsi la décidabilité de cette propriété en temps polynomial, prouvant des résultats de levier et confirmant la clôture par union, ce qui résout une conjecture de Kopczyński dans le cadre ω-régulier.
Cet article généralise la sémantique des langages à appel par valeur en montrant que la représentation des espaces fonctionnels avec itération gardée nécessite des monades paramétrées, offrant ainsi une description de la garditude comme une propriété catégorique intrinsèque des programmes.
Les auteurs présentent un algorithme permettant d'énumérer les réponses aux requêtes MSO sur des arbres non rangés compressés par un programme linéaire, avec un temps de prétraitement linéaire par rapport à la taille de la compression et un délai de sortie linéaire, tout en supportant des mises à jour de libellés en temps logarithmique.
Cet article démontre que les dynamiques de graphes causaux, qui modélisent la transformation synchrone et déterministe de graphes de ports, peuvent être comprises comme des extensions de Kan, révélant ainsi la validité de la formalisation des transformations globales pour ce modèle et mettant en lumière l'universalité des dynamiques causales monotones.
Cet article propose une théorie et des algorithmes pour classer les transformations de graphes en vue de leur réparation en utilisant des conditions d'application faibles dites « indicatrices d'altération » et « indicatrices de réparation », permettant ainsi d'évaluer et d'optimiser le gain potentiel de réparation avant l'exécution.