Automates à contraintes semilinéaires = Automata with a semilinear constraint
Bibliographic record
Abstract
Cette thèse présente une étude dans divers domaines de l'informatique\nthéorique de modèles de calculs combinant automates finis et contraintes\narithmétiques. Nous nous intéressons aux questions de décidabilité,\nd'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la\nlogique, l'algèbre et aux applications. Cette étude est présentée au travers\nde quatre articles de recherche.\n\nLe premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess\ndes automates de Parikh et en définit des généralisations et restrictions.\nL'automate de Parikh est un point de départ de cette thèse; nous montrons que\nce modèle de calcul est équivalent à l'automate contraint que nous\ndéfinissons comme un automate qui n'accepte un mot que si le nombre de fois\nque chaque transition est empruntée répond à une contrainte arithmétique.\nCe modèle est naturellement étendu à l'automate de Parikh affine qui\neffectue une opération affine sur un ensemble de registres lors du\nfranchissement d'une transition. Nous étudions aussi l'automate de\nParikh sur lettres: un automate qui n'accepte un mot que si le nombre de\nfois que chaque lettre y apparaît répond à une contrainte arithmétique.\n\nLe deuxième article, Bounded Parikh Automata, étudie les langages\nbornés des automates de Parikh. Un langage est borné s'il existe des\nmots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire\nw_1...w_1w_2...w_2...w_k...w_k. Ces langages sont\nimportants dans des domaines applicatifs et présentent usuellement de bonnes\npropriétés théoriques. Nous montrons que dans le contexte des langages\nbornés, le déterminisme n'influence pas l'expressivité des automates de\nParikh.\n\nLe troisième article, Unambiguous Constrained Automata, introduit les\nautomates contraints non ambigus, c'est-à-dire pour lesquels il\nn'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous\nmontrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de\nmeilleures propriétés de clôture que l'automate contraint déterministe. Le\nproblème de déterminer si le langage d'un automate contraint non ambigu est\nrégulier est montré décidable.\n\nLe quatrième article, Algebra and Complexity Meet Contrained Automata,\nprésente une étude des représentations algébriques qu'admettent les automates\ncontraints et les automates de Parikh affines. Nous déduisons de ces\ncaractérisations des résultats d'expressivité et de complexité. Nous\nmontrons aussi que certaines hypothèses classiques en complexité\ncomputationelle sont reliées à des résultats de séparation et de non clôture\ndans les automates de Parikh affines.\n\nLa thèse est conclue par une ouverture à un possible approfondissement, au\ntravers d'un certain nombre de problèmes ouverts.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.003 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.000 | 0.002 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.001 | 0.002 |
| Scholarly communication | 0.003 | 0.004 |
| Open science | 0.001 | 0.002 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.016 | 0.003 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".