Barry Jay dans son livre fait des affirmations audacieuses - essentiellement en disant que, au cœur d'un programme, tout est atomique ou composé. Ensuite, les choses peuvent être facilement itérées, filtrées, mises à jour, simplement en parcourant cette relation de composition. Est-ce une nouvelle...
Un ensemble de mots sur un alphabet fini est sans préfixe s'il n'y a pas deux mots distincts où l'un est un préfixe de l'autre. La question est: Quelle est la complexité de vérifier si un langage régulier donné en NFA contient un sous-ensemble infini sans préfixe? Réponse (grâce à Mikhail Rudoy,...
Est-il possible de construire un algorithme qui prend en entrée un automate de refoulement avec la promesse que le langage accepté par cet automate L ( M ) est un langage déterministe sans contexte et génère un automate de refoulement déterministe N qui accepte précisément le langage accepté par M...
Le problème suivant est décidable: Étant donné une grammaire sans contexte , L ( G ) = ∅ ?GGGL ( G ) = ∅L(G)=∅L(G) = \varnothing Le problème suivant est indécidable: Étant donné une grammaire sans contexte , L ( G ) = A ∗ ?gGGL ( G ) = A∗L(G)=A∗L(G) = A^{\ast} Existe-t-il une caractérisation des...
Cette question est liée à une question récente de Janoma . Contexte Dans la programmation par contraintes, une régulière contrainte globale ccc sur un domaine DDD est une paire (s,M)(s,M)(s, M) avec sss un tuple de variables (la portée) et MMM DFA sur le domaine DDD . Une affectation θθ\theta à sss...
Soit un langage et une fonction sur deux paramètres avec la propriété que pour tout et , renvoie un élément de si et seulement si et sont des éléments de :f : Σ ⋆ × Σ ⋆ → Σ ⋆ x y f L x y LLLLF: Σ⋆× Σ⋆→ Σ⋆f:Σ⋆×Σ⋆→Σ⋆f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\starXxxyyyFFfLLLXXxyyyLLL F( x ,y)...
EDIT (Par Tara B): Je serais toujours intéressé par une référence à une preuve de cela, car je devais le prouver moi-même pour mon propre papier. Je cherche la preuve du Théorème 4 qui apparaît dans cet article: Une hiérarchie infinie d'intersections de langues sans contexte par Liu et Weiner....
Je comprends que les affirmations suivantes sont vraies: Deux dérivations distinctes d'une chaîne dans un CFG donné peuvent parfois attribuer le même arbre d'analyse à la chaîne. Lorsqu'il existe des dérivations d'une chaîne dans un CFG donné qui attribuent différents arbres d'analyse, le CFG est...
Considérez le problème suivant: Étant donné deux chaînes x, y, décidez s'il existe un homomorphisme de chaîne f tel que f (x) = y. Il est facile de montrer que ce problème est dans . Y a-t-il d'autres choses que nous pouvons dire sur ce problème? Par exemple, est-ce en , ou même en ?c o N P...
Un système d'addition vectorielle (VAS) est un ensemble fini d' actions A⊂ZdA⊂ZdA \subset \mathbb{Z}^d . NdNd\mathbb{N}^d est l'ensemble des marquages . Une course est un mot non vide de marques m0m1…mnm0m1…mnm_0 m_1\dots m_n st ∀i∈{0,…,n−1},mi+1−mi∈A∀i∈{0,…,n−1},mi+1−mi∈A\forall i \in \{0, \dots,...
Un DFA ou un NFA lit une chaîne d'entrée avec une seule tête, se déplaçant de gauche à droite. Il semble naturel de s'interroger sur les machines à états finis qui ont plusieurs têtes , chacune se déplaçant à travers l'entrée de gauche à droite, mais pas nécessairement au même endroit dans l'entrée...
Salut à tous, j'essaie actuellement de trouver un sujet de thèse de master solide se rapportant à une branche de la théorie des automates ou lié aux langages formels. J'essaie de générer de bonnes idées sur ce qu'est un sujet acceptable, quelque chose d'ambitieux mais quelque chose de faisable en...
J'essaie de dresser une taxonomie d'algorithmes pour transformer des expressions régulières en automates afin d'effectuer des tests empiriques de leurs propriétés de complexité dans des domaines spécifiques. Je connais plusieurs des plus grands noms, par exemple, Thompson "Algorithme de recherche...
Énoncé du problème: Soit un automate de refoulement (potentiellement non déterministe) et soit son alphabet d'entrée. Y a-t-il un mot st accepté par ?A w ∈ A ∗ | w | ≤ k MMMMAA\cal Aw∈A∗w∈A∗w \in \cal A^*|w|≤k|w|≤k|w| \leq kMMM Ce problème est-il NP-complet? At-il été étudié? Existe-t-il un...
Soit un langage sans contexte. Définir soit à la fermeture avant et postfixe de , en d' autres termes, contient l' ensemble des des préfixes des suffixes de » et, et par conséquent elle - même. Ma question: si est sans contexte et a une grammaire non ambiguë, est-ce la même chose pour ?p p c ( L )...
Dans le chapitre 13 «Objets atomiques» du livre «Algorithmes distribués» de Nancy Lynch, la linéarisation (également connue sous le nom d'atomicité) s'est avérée être une propriété de sécurité. C'est-à-dire que sa propriété de trace correspondante est non vide, fermée par préfixe et fermée par...
Cette question est de savoir s'il existe des tarpits de Turing réversibles connus, où "réversible" signifie au sens d' Axelsen et de Glück , et "tarpit" est un concept beaucoup plus informel (et pourrait ne pas être un très bon choix de mot), mais je ferai de mon mieux pour expliquer ce que je veux...
Quelle est l'approche standard pour minimiser Büchi-Automata (ou aussi Müller-Automata)? Le transfert de la technique habituelle à partir de mots finis, c'est-à-dire la mise à égalité de deux états si les mots "en cours d'exécution" des états acceptés sont les mêmes, ne fonctionnera pas. Par...
Il existe un problème ouvert dans les langages formels connu sous le nom de problème de séparation; qui est brièvement indiqué comme étant donné deux chaînes distinctes de longueur , la taille d'un DFA est nécessaire pour les "séparer", ce qui signifie accepter une chaîne mais rejeter l'autre.nnn...
Soit un nombre . Considérons la langue suivante L n = {nnn .Ln= {w w|w ∈ { 0 , 1 }n}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} En termes, est l'ensemble des chaînes de copie de longueur 2 n .LnLnL_n2 n2n2n Considérons la fonction de complexité d'état suivante telle que s ( n...