Une ambiguïté constante peut-elle réduire la complexité de l'état d'une langue régulière?

Nous disons que NFA est constamment ambigu s'il existe telle sorte que tout mot est accepté par ou (exactement) chemins. $M$ $k\in \mathbb{N}$ $w\in \Sigma^*$ $0$ $k$

Si l'automate est constamment ambigu pour , alors est appelé FA sans ambiguïté (UFA). $M$ $k=1$ $M$

Soit une langue régulière. $L$

Un automate constamment ambigu pour peut-il être plus petit que le plus petit UFA qui accepte ? Combien pourrait-il être plus petit? $M_c$ $L$ $L$

L'automate Finitely ambigu peut-il être exponentiellement plus petit que le plus petit CFA pour la même langue?

On sait qu'il existe des automates finement ambigus (il existe , de sorte que chaque mot est accepté par jusqu'à chemins) qui sont exponentiellement plus petits que le plus petit UFA pour le même langage, mais je n'ai rien vu d'ambiguïté constante. $k$ $k$

En outre, voici une question connexe que j'ai publiée ici il y a quelques mois.

ÉDITER:

La réponse de Domotorp montre que le est polynomialement réductible à l' , mais ne répond pas à la question de savoir si nous pouvons gagner cette réduction d'espace polynomial par les . $CFA$ $UFA$ $CFA$

La nouvelle question devient donc: combien plus petit (linéairement / quadratique / etc.) Un peut-il être comparé à l' minimal ? pour la même langue? $CFA$ $UFA$

les transitions elles autorisées?

ϵ

$\epsilon$

Denis

Cela peut être utile: dans Kupke, On Separating Constant from Polynomial Ambiguity of Finite Automata, la hiérarchie suivante est présentée: Je n'ai pas vérifié le document associé car il est derrière paywall.

dfa ≺_{2^{n}} unfa ≺_{2^{n}} cafa ≺_{2^{n}} ??? ≺_{2^{n}} pafa ≺_{2^{n}} n f a

$\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n} \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$

Marzio De Biasi

Merci @MarzioDeBiasi, mais malheureusement cela n'aide pas (j'avais aussi bon espoir quand j'ai vu la présentation). Ils utilisent une notation différente de celle que j'utilise (et j'ai vu dans différents articles). Leur «ambiguïté constante» est ce que j'ai appelé l'ambiguïté finie, donc la relation entre leur Cafa et l'UFA était déjà connue de moi. Étant donné que mon application compte les solutions aux problèmes de PNJ, mon langage est toujours fini, et en tant que tel, chaque mot est accepté par les chemins , qu'ils ont appelés "constants".

O (1)

$O(1)$

Je me demande si ma définition aide à réduire la complexité des états, car j'ai CFA qui est exponentiellement plus petit que le plus petit UFA que je connaisse à construire, et je me demandais s'il était possible qu'il n'y ait pas de petit UFA pour le langage.

@Denis, oui, mais cela vous aiderait-il à réduire la complexité de l'état? Je suppose que vous ne pouvez réduire le nombre d'arêtes que par de tels mouvements.

Réponses:

Je prétends que si pour une langue , il est analyste financier avec des états et ou accepter des chemins pour chaque mot, alors il y a un APU avec états. L'idée de base est que les états de l'UFA sont les c-tuples (ordonnés) des états du CFA et il accepte si et seulement si tous les c états acceptent. Bien sûr, nous devons également nous assurer qu'il s'agissait bien de calculs différents et que nous ne comptons pas tous les permutations, donc pour ceux - ci nous avons besoin supplémentaire les bits de mémoire. $s$ $0$ $c$ $C_ss^c$ $c!$ $C_s$

Une description un peu plus détaillée de l'idée de base: si est un état de l'UFA, alors il a une transition de celui-ci (en lisant une lettre ) à l'état si et seulement si le CFA a une transition (lecture de la lettre ) de à pour chaque . Un état $(s_1,\ldots,s_c)$ $a$ $(s_1',\ldots,s_c')$ $a$ $s_i$ $s_i'$ $i$ $(s_1,\ldots,s_c)$ accepte si et seulement si accepte pour chaque . Bien sûr, l'état de départ de l'UFA est où est l'état de départ du CFA. $s_i$ $i$ $(s_0,\ldots,s_0)$ $s_0$

Le problème avec ce qui précède est que les exécutions simulées du CFA peuvent être les mêmes. Nous ajoutons donc quelques informations supplémentaires, codées, disons, dans un graphique sur sommets qui a une arête entre le sommet et le sommet si pendant la course jusqu'à présent au moins une fois que nous avons eu . $c$ $c$ $i$ $j$ $c_i\ne c_j$

Maintenant, nous avons encore un problème, que nous avons tout compté fois en raison des permutations possibles. Nous pouvons remédier à cela en exigeant que si les états -th et -th étaient les mêmes jusqu'à présent et à l'étape suivante, ils différeraient, alors à l'étape suivante, le état devrait avoir un indice plus grand. $c!$ $i$ $j$ $i$

domotorp
la source

Merci d'avoir répondu à @domotorp. Malheureusement, je ne peux pas dire que je le comprends. Pouvez-vous donner plus de détails (par exemple, comment la preuve de primauté serait-elle encodée?). Merci !

J'ai réalisé de toute façon qu'il existe également un UFA pour cette langue, alors oubliez-le. Qu'en est-il du reste de ma réponse?

domotorp

Je ne suis pas sûr de suivre. Si

est CFA avec

, cela ne signifie pas qu'il ne peut y avoir que

chemins pour chaque mot

, juste que seulement

d'entre eux se terminent dans un état acceptant. Quels seraient les états de l'UFA? Pouvez-vous essayer de le formaliser?

M

$M$

k = c

$k=c$

c

$c$

w

$w$

c

$c$

Voilà, j'espère que maintenant c'est clair.

domotorp