Comment est difficile de démêler une chaîne?

117

Un mélange de deux chaînes est formé en intercalant les caractères dans une nouvelle chaîne, en maintenant les caractères de chaque chaîne dans l'ordre. Par exemple, MISSISSIPPIest un mélange de MISIPPet SSISI. Permettez-moi d'appeler un carré de corde s'il s'agit d'un mélange de deux chaînes identiques. Par exemple, ABCABDCDest carré, car c'est un mélange de ABCDet ABCD, mais la chaîne ABCDDCBAn'est pas carrée.

Existe-t-il un algorithme rapide permettant de déterminer si une chaîne est carrée ou est-ce NP-difficile? L'approche de programmation dynamique évidente ne semble pas fonctionner.

Même les cas spéciaux suivants semblent difficiles: (1) des chaînes dans lesquelles chaque caractère apparaît au maximum quatre fois sur six , et (2) des chaînes avec seulement deux caractères distincts. Comme Per Austrin le souligne ci-dessous, le cas particulier où chaque caractère apparaît au plus quatre fois peut être réduit à 2SAT.


Mise à jour: Ce problème a une autre formulation qui peut rendre une preuve de dureté plus facile.

Considérons un graphe G dont les sommets sont les entiers 1 à n; identifier chaque bord avec l'intervalle réel entre ses extrémités. Nous disons que deux arêtes de G sont imbriquées si un intervalle contient correctement l'autre. Par exemple, les arêtes (1,5) et (2,3) sont imbriquées, mais (1,3) et (5,6) ne le sont pas et (1,5) et (2,8) ne le sont pas. Une correspondance dans G est non imbriquée si aucune paire d'arêtes n'est imbriquée. Existe-t-il un algorithme rapide pour déterminer si G a une correspondance parfaite non imbriquée ou si ce problème est NP-difficile?

  • Supprimer une chaîne équivaut à rechercher une correspondance parfaite non imbriquée dans une union disjointe de cliques (avec des bords entre des caractères égaux). En particulier, la suppression d'une chaîne binaire équivaut à la recherche d'une correspondance parfaite non imbriquée dans une union disjointe de deux cliques. Mais je ne sais même pas si ce problème est difficile pour les graphiques généraux, ou facile pour toute classe de graphiques intéressante.

  • Il existe un algorithme polynomial facile à trouver non parfait passage appariements.


Mise à jour (24 juin 2013): le problème est résolu! Il existe maintenant deux preuves indépendantes indiquant que l'identification de chaînes carrées est NP-complète.

Il existe également une preuve plus simple que trouver des correspondances parfaites non imbriquées est NP-difficile, en raison de Shuai Cheng Li et Ming Li en 2009. Voir " Deux problèmes non résolus de modèles à 2 intervalles ", Théorie de l'informatique 410 (24–25). ): 2410–2423, 2009.

Jeffε
la source
2
La séquence A000984 n’est-elle pas simplement le "nombre de valeurs possibles d’un nombre binaire à 2 * n bits pour lequel la moitié des bits sont activés et la moitié sont désactivées"?
Travis Brown
5
@ Travis, à moins que je ne comprenne mal: Pour n = 4, 10000111 est un nombre binaire de 2 * n bits pour lequel la moitié des bits sont activés et l'autre moitié désactivée, mais qui n'est pas un carré, tel que défini. Suivant cette logique, puisque les carrés sont un sous-ensemble strict de l'ensemble qui génère A000984, les valeurs des carrés sur un alphabet binaire doivent être inférieures à des indices égaux dans la séquence - non?
Daniel Apon
1
Observation: En utilisant le formalisme de graphe, prenons 2n le nombre de sommets de G. Supposons que G 'soit un graphe obtenu à partir du graphe linéaire de G en ajoutant les arêtes entre les sommets correspondant aux arêtes imbriquées de G. Le problème est de savoir si G' a un ensemble indépendant de taille n. Il existe différentes classes de graphes dans lesquelles un ensemble maximum indépendant peut être calculé en temps polynomial. Si nous allons dans cette voie, la question est: Quelles sont les propriétés intéressantes de G′? (plus)
Tsuyoshi Ito le
2
@Radu: Je ne pense pas que la fraction de carrés en non-carrés (sur des alphabets binaires) converge vers 1/3. J'ai fait des simulations de Monte-Carlo qui indiquent une convergence lente à 1/2. Par conséquent, dans la limite, pratiquement toutes les chaînes binaires avec des nombres pairs de 0 et 1 sont des carrés. Cela me surprend et peut être exploitable dans un algorithme. Pour les grands alphabets, la fraction de carrés semble converger rapidement vers 0.
Martin Berger
8
Puisque cette question est mentionnée dans l'article de blog d'aujourd'hui, voyons si nous pouvons obtenir un regain d'intérêt pour résoudre ce problème. Cela fait un an que cette question a été posée et nous avons depuis gagné beaucoup de nouveaux utilisateurs. J'ai mis en place une prime de 100 représentants pour la question.
Alex ten Brink

Réponses:

66

Michael Soltys et moi avons réussi à prouver que le problème consistant à déterminer si une chaîne de caractères peut être écrite sous forme de mélange carré est NP complet. Ceci s'applique même sur un alphabet fini avec seulement symboles distincts, bien que notre preuve soit écrite pour un alphabet avec 9 symboles. Cette question reste ouverte pour les alphabets plus petits, par exemple avec seulement 2 symboles. Nous n’avons pas examiné le problème dans la mesure où chaque symbole n’apparaît que six fois (ou plus généralement un nombre de fois constant); donc cette question est toujours ouverte.7926

La preuve utilise une réduction de Partition. Il est trop long de poster ici, mais une pré-impression, "Le démêlage d'une chaîne est NP- dur", est disponible sur nos pages Web à l'adresse:3NP

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

et

http://www.cas.mcmaster.ca/~soltys/#Papers .

Le document a été publié dans le Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Sam Buss
la source
11
Impressionnant!! (Et à mon immense soulagement, sérieusement non trivial.)
Jeffε
15
Merci. StackExchange était notre source pour cette question. C'est une excellente ressource!
Sam Buss
9
@SamBuss une petite demande: pendant que vous citez la question de Jeff, vous ne mentionnez que la solution de Per Austrin dans le texte. Si vous examinez les réponses, vous pouvez également générer une citation formelle des réponses (cliquez sur le bouton de partage et sur le lien "Citer"). De cette manière, vous pouvez également générer une citation appropriée pour la réponse de Per. Je le mentionne uniquement pour que les personnes qui apportent des contributions formelles sur le site puissent également obtenir une reconnaissance formelle. Merci ! et félicitations pour résoudre ce problème
Suresh Venkat
2
@SureshVenkat. Merci pour le conseil: c'est utile. J'ai ajouté ceci à la version en ligne du document.
Sam Buss
Le problème de la reconnaissance d'un mélange aléatoire carré s'est révélé difficile, même avec un alphabet binaire: sciencedirect.com/science/article/pii/S0304397519300258
a3nm
58

Dans le cas particulier que vous mentionnez lorsque chaque caractère apparaît au plus quatre fois, il y a une simple réduction à 2-SAT (sauf si quelque chose me manque ...), comme suit:

Le point crucial est que pour chaque personnage, il existe (au plus) deux manières valides de faire correspondre les occurrences du personnage (la troisième possibilité sera l’imbrication). Utilisez une variable booléenne pour représenter laquelle des deux correspondances est choisie. Maintenant, une affectation à ces variables donne un démêlage valide de la chaîne ssf pour chaque paire d'arêtes imbriquées, mais les deux n'ont pas été choisies. Cette condition peut être décrite avec précision par une disjonction des variables (éventuellement inversées) correspondant aux deux caractères impliqués.

Par Austrin
la source
Agréable. La même idée se généralise aux chaînes où chaque caractère apparaît au plus six fois, mais le résultat est une instance de 5-SAT. :-(
Jeffε
2
Cette réponse est le favori pour gagner la prime.
Jeffε
cela semble donc prouver que le problème est NPC et pourquoi nous avons besoin de longues preuves de conférence et de journal?
T ....
@Turbo Beaucoup de retard, mais cela ne prouve pas que le problème est NPC car 2-SAT n'est pas NPC; c'est dans P.
Steven Stadnicki
Cette réduction à 2-SAT fonctionne-t-elle si la taille de l'alphabet n'est pas limitée?
Mohammad Al-Turkistany
11

Voici un algorithme qui a peut-être une chance d'être correct bien que cela semble difficile à prouver et je ne parierais pas la maison dessus ...

GeGee

GGGG

>1

Après le choix gourmand, nous purgeons à nouveau le graphique, etc., et le processus se termine lorsque le graphique est (espérons-le) une correspondance parfaite non imbriquée.

Au début, je pensais que cela ressemblait plus ou moins à une petite anticipation dans l’algorithme glouton et que cela ne fonctionnait pas vraiment, mais j’ai trouvé étonnamment difficile de trouver un contre-exemple.

Par Austrin
la source
Je suis sceptique quant à la deuxième phase gourmande, mais purger le graphique semble utile. Dans le contexte de chaîne d'origine, où le graphique est l'union disjointe de cliques, pouvez-vous nous dire quelque chose à propos de la structure du graphique purgé? Est-ce toujours une union disjointe de cliques? (En d'autres termes, pouvez-vous partitionner les occurrences de chaque caractère dans la chaîne d'entrée afin que des caractères de parties différentes ne puissent pas être
identiques
2
Pour la deuxième question, considérons la chaîne 'aaaa'. La purge enlève les bords 1-4 et 2-3, donnant un cycle de 4. Deux variantes de la deuxième étape gourmande qui seraient également suffisantes et pour lesquelles je n’ai trouvé aucun contre-exemple sont les suivantes: 1) Un graphe purgé a une correspondance parfaite non imbriquée s’il a une correspondance parfaite (cela semble incomparable à l’étape gourmande). . 2) Dans un graphe purgé avec une correspondance parfaite non imbriquée, chaque bord est utilisé dans une certaine correspondance parfaite non imbriquée (ceci est plus fort que l'étape gourmande et le premier élément, il devrait donc être plus facile à réfuter).
Par Austrin
11

La solution proposée par Sam Buss et moi-même en novembre 2012 (montrant que la suppression d'une case de NP-hard par une réduction de 3-Partition) est désormais un article publié dans le Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Michael Soltys
la source
2
Cela devrait vraiment être une modification de la réponse précédente de Sam Buss, plutôt qu'une réponse séparée. Vous pouvez cliquer sur "modifier" pour suggérer une modification à la réponse de quelqu'un d'autre, et votre modification sera examinée par les autres utilisateurs du site.
DW
11

Romeo Rizzi et Stéphane Vialette prouvent que la reconnaissance des chaînes carrées est NP-complète dans leur document de 2013 intitulé " Reconnaître les mots qui sont des carrés pour le produit Shuffle ", en réduisant le plus long problème binaire de sous-séquence. Ils affirment que la complexité de la récupération des chaînes binaires est toujours ouverte.

Une preuve encore plus simple que la recherche de la correspondance parfaite non imbriquée est NP-complète est donnée par Shuai Cheng Li et Ming Li dans leur document de 2009 " Sur deux problèmes non résolus de modèles à 2 intervalles ". Cependant, ils utilisent une terminologie héritée de la bioinformatique. Au lieu de "correspondance parfaite non imbriquée", ils l'appellent le problème " DIS-2-IP- ". L'équivalence entre les deux problèmes est décrite par Blin, Fertin et Vialette :{<,}

Le problème 2-IP-DIS- a une formulation immédiate en termes de correspondances contraintes dans les graphes généraux: Soit un graphe associé à un ordre linéaire des sommets de , le 2-IP -DIS- est équivalent à trouver une cardinalité maximale correspondant à en avec la propriété qui, pour deux arêtes distinctes quelconques et de ni les et ni{<,}GπG{<,}MG{u,v}{u,v}Mmin{π(u),π(v)}<min{π(u),π(v)}max{π(u),π(v)<max{π(u),π(v)}min{π(u),π(v)}<min{π(u),π(v)} et se produisent.max{π(u),π(v)}<max{π(u),π(v)}

Mise à jour (25 février 2019): Bulteau et Vialette ont montré que le problème de décision consistant à libérer une chaîne binaire est NP-complet dans leur document. Reconnaître les carrés de mélange binaires est NP-difficile .

Mohammad Al-Turkistany
la source
Je ne vois pas la connexion, et je ne vois pas où les auteurs prétendent que le fait de mélanger une chaîne est équivalent à leur problème.
Suresh Venkat
2
Ils ne disent pas que cela équivaut à un remaniement; c'est un problème plus général.
Jeffe
@SureshVenkat J'ai modifié ma réponse, j'espère qu'elle est plus claire. Fondamentalement, ce qu'ils disent dans la note de bas de page, c'est que deux arêtes quelconques dans la correspondance ( ) ne sont pas imbriquées. M
Mohammad Al-Turkistany
Dans la version publiée actuelle, l'équivalence est indiquée à la page 320. books.google.com/…
Mohammad Al-Turkistany
Edité pour enterrer la lede .
Jeffe
9

est-ce que cela aide?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

Aaron Sterling
la source
7
Belle référence. Il est difficile de voir comment les résultats s'appliqueraient à mon problème, mais les techniques pourraient peut-être aider. Il est facile de savoir si une chaîne donnée X est un mélange aléatoire de deux copies d'une autre chaîne donnée Y. Le document joint prouve qu'il est difficile de décider si une chaîne donnée X est un mélange aléatoire d' un nombre quelconque de copies d'une autre chaîne donnée Y. Je veux savoir si une chaîne donnée X est un mélange de deux copies de la chaîne SOME INCONNU Y.
Jeffε
5

N'OUBLIEZ JAMAIS, CETTE RÉPONSE EST FAUX. Il échoue à l'entrée "AABAAB": une correspondance avide des deux premiers A l'un avec l'autre rend impossible la correspondance des symboles restants. Je la laisse plutôt que de la supprimer pour aider les autres à ne pas commettre la même erreur.

Il me semble qu'il est toujours prudent d'associer chaque caractère successif du supposé carré à un autre personnage égal qui se trouve le plus tôt possible. C'est-à-dire que l'algorithme temporel linéaire suivant devrait fonctionner:

Boucle à travers chaque position i dans la chaîne d'entrée, i = 0, 1, 2, ... n. Pour chaque position i, vérifiez si cette position a déjà été comparée à une position antérieure de la chaîne. Si ce n'est pas le cas, comparez-le avec un caractère égal qui vient après la dernière position déjà appariée, sinon apparaît le plus tôt possible dans la chaîne. Si aucune correspondance n'est trouvée pour un caractère, déclarez que l'entrée n'est pas un carré; sinon, c'est l'ensemble des caractères de la première paire de chaque match.

La voici en Python:

def sqrt (S):
    allumettes = []
    i, j = 0, 0
    pendant que je <len (S):
        si j <len (correspond) et correspond à [j] [1] == i:
            i + = 1
            j + = 1
            Continuez
        si correspond:
            k = correspond à [-1] [1] + 1
        autre:
            k = 1
        tandis que k <len (S) et S [k]! = S [i]:
            k + = 1
        si k> = len (S):
            augmenter Exception ("Pas un carré")
        matches.append ((i, k))
        i + = 1
    retourne "" .join (S [a] pour a, b dans les correspondances)

print sqrt ("ABCABDCD")

Ici, i est la variable de boucle principale (la position que nous essayons de faire correspondre), j est un pointeur dans le tableau de paires appariées qui accélère la vérification de la correspondance de la position i et k est un index utilisé pour rechercher le caractère qui correspond à celui de la position i. C'est un temps linéaire car i, j et k augmentent de façon monotone à travers la chaîne et chaque itération de la boucle interne en augmente une.

David Eppstein
la source
4
Été là. C'est fait. :-)
Jeffε
5

Mise à jour: Il n’a aucun sens de parler de la difficulté de trouver une correspondance parfaite non imbriquée et non croisée, lorsque les étiquettes sont comprises entre 1 et n, car il n’en existe qu’une seule. (Oui, je me donne des coups de pied.) Cependant, cela aurait du sens étant donné une plus grande plage sur les étiquettes ... donc je vois encore un peu d'espoir, mais cela pourrait être assez inutile après tout. J'aurais certainement à en suivre un peu plus.


Je peux comprendre pourquoi il peut être difficile de trouver une correspondance non-imbriquée et non-croisée. Laissez-moi appeler une telle correspondance une correspondance disjointe . Je ne sais pas dans quelle mesure cela aide, mais permettez-moi de présenter le raisonnement de toute façon. (Je devrais souligner que mon argument, tel qu'il est rédigé ici, n'est pas complet et que les détails que je laisse de côté sont peut-être cruciaux. Cependant, j'imagine que cela pourrait être un début.)

Je vais commencer par un problème légèrement différent. Soit un graphe dont les arêtes sont colorées avec couleurs et dont les sommets sont étiquetés de à , existe-t-il une correspondance disjointe contenant exactement une arête de chaque couleur? Ce problème semble être NP-difficile (l'argument pour cela est à la fois complet et simple - à moins que je manque quelque chose). La réduction génère un graphique qui est une union disjointe de cliques.Gk1n

La réduction provient de Disjoint Factors , un problème NP-complet introduit dans [1]. Un exemple de facteurs disjoints est donné par une chaîne sur un alphabet de taille , et la question est de savoir s'il existe facteurs disjoints, où un facteur est une sous-chaîne qui commence et se termine par la même lettre; et deux facteurs sont disjoints s'ils ne se chevauchent pas dans la chaîne (notez que l'imbrication, en particulier, est également interdite).kk

Permettez-moi de noter par , les éléments de l’ alphabet de taille associé à l’instance Disjoint Factors.a1,,akk

Soit une instance de facteurs disjoints, c'est-à-dire une chaîne de longueur , créez un graphique comportant sommets avec des étiquettes de sommet de à . Ajoutez un bord entre les sommets et si les positions correspondantes ont la même lettre (disons ) et colorez également le bord avec la couleur .nn1nuvai(u,v)i

La preuve de la réduction découle essentiellement des définitions. Étant donné facteurs disjoints, nous avons clairement une correspondance colorée -disjoint, nous sélectionnons simplement les bords donnés par les facteurs disjoints, et il est facile de voir que la correspondance résultante est à la fois colorée et disjointe. A l' inverse, s'il y a un correspondant de -disjoint coloré, nous avons k facteurs disjoints, un pour chaque lettre, parce que la correspondance est colorée (et prend donc un facteur par lettre), et est disjointe (donc les facteurs correspondants ne se chevauchent pas )kkk

Pour supprimer les couleurs et faire en sorte que la correspondance soit parfaite, même sur une plage éventuellement plus large , apportez les modifications suivantes au graphique ainsi créé:

Soit le sous-ensemble de sommets dont les étiquettes sont des positions associées à la lettre . Si a des sommets , ajoutez nouveaux sommets et un graphe bipartite complet entre et les nouveaux sommets ajoutés. Répétez, bien sûr, pour chaque lettre. a U a A ( A - 2 ) U aUaaUaA(A2)Ua

En gros, si le graphe doit induire une correspondance parfaite, les sommets nouvellement introduits doivent correspondre aux sommets de , et ils tous sauf une paire de sommets et le bord entre les sommets restants correspondra au facteur disjoint. . Je n'ai pas encore déterminé les nombres que l'on doit associer aux sommets nouvellement ajoutés ... Notez qu'ils doivent l'être pour que la correspondance résultante soit disjointe. J'ai juste le sentiment (lire: espérons) que cela peut être fait!Ua

[1] Sur les problèmes sans noyaux polynomiaux , Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows et Danny Hermelin, J. Comput. Syst. Sci.

Neeldhara
la source
3
Je suis confus. (1,2), (3,4), (5,6), ..., (n-1, n) n'est-il pas la SEULE correspondance parfaite?
Jeffε
Une fois que je passe au scénario de «correspondance parfaite», je modifie la construction et ajoute de nombreux nouveaux sommets (notez que j'ajoute | U_a | -2 nouveaux sommets pour chaque a de l'alphabet). Ainsi, n va exploser en conséquence - à peu près à 2n-2k, pour un alphabet de taille k. J'espère que j'ai bien précisé que la réduction est incomplète en ce que je n'ai pas précisé quels nombres sont attribués aux nouveaux sommets, mais j'espère que cela pourra être prolongé sans trop de difficulté. Cependant, je dois certainement y réfléchir avant de pouvoir en dire plus.
Neeldhara
1
Je pense que le but de JeffE est qu'il est facile de trouver une correspondance parfaite non-imbriquée et non croisée (ou en signaler l'absence), car il n'y a qu'une seule possibilité.
Tsuyoshi Ito
2
Je ne parle pas du contenu de votre idée de preuve, mais de la première phrase de votre réponse: «Je peux imaginer pourquoi il pourrait être difficile de trouver une correspondance parfaite qui soit non imbriquée et non croisée.» Cette tâche est facile pour la raison pour laquelle JeffE a écrit.
Tsuyoshi Ito
2
Sans la contrainte de coloration imposée par le problème du facteur disjoint (au plus un bord de chaque couleur), il est également facile de trouver des correspondances disjointes maximales.
Jeffε
1

L'approche ne fonctionne pas: décomposer un carré mélangé en supprimant deux lettres correspondantes ne donne pas des carrés mélangés ... Voir les commentaires de Radu ci-dessous.


Σ

S(XY)A(X,Y)(1)A(aX1,aX2Y1Y2)A(X1,Y1)A(X2,Y2)(2)A(ε,ε)ε(3)
aΣε

X1Y1Y1X2Y2Y1Y2X1X2

abcabdcd

S(abcabdcd)A(abc,abdcd)(by 1,X=abc,Y=abdcd)A(bc,bdcd)A(ε,ε)(by 2,X1=bc,Y1=bdcd,X2=Y2=ε)A(c,c)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(ε,ε)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(d,d)A(ε,ε)(by 3)A(d,d)A(ε,ε)(by 3)A(ε,ε)A(ε,ε)A(ε,ε)(by 2)3εi.e. success

0011

S(0011)A(0,011)A(ε,ε)A(1,1)A(1,1)ε

XY

Sylvain
la source
Y at-il une dérivation qui prend S (0011) à ? (Il devrait y en avoir un.)ϵ
Radu GRIGore
Je ne pense pas.
Serge Gaspers
Aussi, A (10,011010) -> A (0,101) A (0,0) -> , mais je crois que 10011010 n’est pas un carré. ϵ
Radu GRIGore
Merci pour les retours J'ai un peu changé la grammaire et j'ai même une petite intuition avec laquelle cela pourrait fonctionner.
Sylvain
3
Je vous en prie. Voici plus, pour la grammaire mise à jour :) A (00,000110) -> A (0,011) A (0,0) -> , mais 00000110 n'est pas un carré. En outre, il semble n'y avoir aucune dérivation pour 100110101010, qui est un carré. ϵ
Radu GRIGore
1

Mise à jour: comme le souligne Tsuyoshi Ito dans les commentaires, cet algorithme a une durée d'exécution exponentielle.

Message original:

Voici comment je programmerais cela dans le monde réel.

On nous donne une chaîne S = (S [1], ..., S [n]). Pour chaque préfixe S_r = (S [1], ..., S [r]), il existe un ensemble {(T_i, U_i)} de paires de chaînes, tel que S_r est un mélange de (T_i, U_i), et T_i est un préfixe de U_i (c.-à-d. que U_i commence par «T_i). S_r est lui-même un carré si et seulement si cet ensemble contient une paire (T_i, U_i) avec T_i = U_i.

Maintenant, nous n'avons pas besoin de générer toutes ces paires; il suffit de générer le suffixe V_i de chaque chaîne U_i obtenue en supprimant sa copie de T_i. Cela éliminera un nombre (éventuellement exponentiel) de doublons non pertinents. Maintenant, S_r est un carré si et seulement si cet ensemble de suffixes contient la chaîne vide. Donc, l'algorithme devient:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

Par exemple, si S est AABAAB:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

Nous pouvons supprimer tous les suffixes qui sont plus de la moitié de la longueur de la chaîne d'entrée. Cela simplifie donc:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

J'ai programmé cela en C ++, et cela fonctionne sur tous les exemples donnés ici. Je peux poster le code, si quelqu'un est intéressé. La question est la suivante: la taille de SuffixSet peut-elle croître plus rapidement que polynomial?

TonyK
la source
3
J'ai aussi essayé cela, mais des expériences ont montré que la taille de SuffixSet semble croître de manière exponentielle en n si la chaîne d'origine est (AB) ^ n.
Tsuyoshi Ito
1

EDIT: Ceci est une réponse incorrecte.


Sylvain a suggéré un GCR qui, malheureusement, n’était pas approprié pour ces "carrés de mélange". Cependant, je pense qu'il en existe un (EDIT: pas un GCR, voir les commentaires de Kurt ci-dessous!) , Qui se présente comme suit:

S(Y)A(ϵ,Y)(1)A(X,ZY)A(XZ,Y)(2)A(aX,aY)A(X,Y) for every aΣ(3)A(ϵ,ϵ)ϵ(4)

aabbabab(1,2)(3)(2)

100110101010

S(100110101010)A(ϵ,100110101010)(1)A(1001,10101010)(2)A(01,101010)(3)A(011,01010)(2)A(1,010)(3)A(10,10)(2)A(ϵ,ϵ)(3)ϵ(4)

Je n'ai pas élaboré de preuve formelle que cette grammaire capture bien les "carrés de mélange", mais cela ne devrait pas être trop difficile. Sylvain a déjà mentionné que le problème de décision pour les GCR est polynomial.

DaniCL
la source
A(x,ϵ)23
5
@DaniCL, à la réflexion ... Les paramètres dans le RHS des règles de production doivent-ils être des plages contiguës de l'entrée? Je ne l'ai pas vu explicitement dans la définition de l'article de Boullier, mais c'est ce qui semble être utilisé. Dans l'analyse du temps d'exécution de l'algorithme d'analyse, il est indiqué que le nombre d'arguments possibles pour les clauses est O (n ^ 2h), où h est la valeur maximale des clauses et n la longueur en entrée. Dans votre grammaire, XZ en général ne sera pas contigu dans l'entrée d'origine.
Kurt
3
@ Kurt, je pense que vous avez trouvé la faille. Dans un autre article ("nombres chinois, grammaires de MIX, de brouillage et de concaténation de plages"), Boullier déclare explicitement: "Bien entendu, seules les plages consécutives peuvent être concaténées dans de nouvelles plages. Dans tout PRCG, les terminaux, les variables et les arguments d'une clause sont censé être lié aux plages par un mécanisme de substitution ". Cela signifie probablement que ma grammaire n'est pas un GCR valide, que le doute de Radu était raisonnable et que cette approche ne fonctionne pas non plus.
DaniCL
2
@Kurt est correct. Sans la restriction de contiguïté, je suis à peu près sûr de pouvoir créer un ensemble de règles de production qui reconnaissent le langage NP-complet UNARY 3PARTITION. Tout ensemble d’entiers non négatifs peut être codé de manière unaire par une chaîne de caractères dans le langage (1 * 0) ^ *. UNARY 3PARTITION est l'ensemble de toutes ces chaînes dont l'ensemble codé peut être partitionné en sous-ensembles de 3 éléments, tous avec la même somme. (Voir en.wikipedia.org/wiki/3-partition_problem .)
Jeffε,
1
Grammaire pour UNARY 3PARTITION: S (X0Y0Z) -> A (e, X0, Y0, Z); A (W, 1X, Y, Z), A (W, X, 1Y, Z), A (W, X, Y, 1Z) -> A (W1, X, Y, Z); A (W, 0X, 0Y, 0Z) -> B (W, XYZ); B (W, e) -> e; B (W, X0Y0Z) -> C (W, W, X0, Y0, Z); C (W, 1V, 1X, Y, Z), C (W, 1V, X, 1Y, Z), C (W, 1V, X, Y, 1Z) -> C (W, V, X, Y, Z); C (W, e, X, Y, Z) -> B (W, XYZ)
Radu GRIGore