Sistemas de suma de vectores con "obstáculos" finitos

11

Un sistema de adición de vectores (VAS) es un conjunto finito de acciones AZd . Nd es el conjunto de marcas . Una carrera es una palabra no vacía de marcas m0m1mn st i{0,,n1},mi+1miA . Si tal palabra existe, decimos que mn es accesible desde m0 .

Se sabe que el problema de la accesibilidad para los VAS es decidible (pero su complejidad es un problema abierto).

Ahora supongamos que se da un conjunto finito de marcas prohibidas (los obstáculos ). Me gustaría saber si el problema de la accesibilidad aún es decidible.

Intuitivamente, el conjunto finito de obstáculos debería interferir con los caminos solo localmente, por lo que el problema debería ser decidible. Pero no parece trivial probarlo.

EDITAR . Mantendré la respuesta de @ Jérôme como la aceptada, pero me gustaría agregar una pregunta de seguimiento: ¿qué pasa si el conjunto de marcas es Zd ?

Nicolas Perrin
fuente
¿Tiene una buena referencia para hacerse una idea de las ideas detrás de la prueba de decidibilidad? (por ejemplo, diapositivas)
Denis
1
Aquí hay diapositivas: lsv.ens-cachan.fr/Events/Pavas/slides-Leroux.pdf ; y un artículo reciente: hal.archives-ouvertes.fr/hal-00674970 ; Básicamente, la accesibilidad se resuelve mediante un algoritmo de enumeración, basado en el hecho de que si no es accesible desde x , entonces existen dos conjuntos disjuntos Presburger que de alguna manera demostrar la no accesibilidad. Algunas otras diapositivas: automata.rwth-aachen.de/movep2010/abstracts/slides-leroux.pdf . yx
Nicolas Perrin
M Praveen ha dado varias charlas sobre los dos enfoques principales del problema: cmi.ac.in/~praveenm/talks
Sylvain
Para subcampos del problema con obstáculos finitos (por ejemplo, con dimensión restringida), parece que una prueba de capacidad de decisión podría basarse en una propiedad de "eliminación en zigzag". Consulte este documento: labri.fr/perso/leroux/published-papers/LS-concur04.ps , y estas diapositivas: labri.fr/perso/sutre/Talks/Documents/… .
Nicolas Perrin
1
Entiendo por qué el problema se resuelve cuando hay acciones distintas de cero que suman cero, pero ¿qué sucede cuando tales acciones no existen? Parte de su respuesta ha sido cortada del comentario :)
Nicolas Perrin

Respuestas:

5

La idea se basa en una discusión que tuve con Grégoire Sutre esta tarde.

El problema es decidible de la siguiente manera.

Una red Petri es un conjunto finito de pares en N d × N d llamados transiciones. Dada una transición t = ( u , v ) , denotamos por t la relación binaria definida en el conjunto de configuraciones N d por x ty si existe un vector zN d tal que x = u + z yTNd×Ndt=(u,v)tNdxtyzNdx=u+z . Denotamos por T la relación de accesibilidad de un pasotT t . El cierre reflexivo y transitivo de esta relación se denota por T .y=v+zTtTtT

Sea el orden parcial clásico por componentes sobre N d y definido por ux si existe zN d tal que x = u + z . El cierre hacia arriba de un conjunto X de N d es el conjunto X de vectores { vN dxXNduxzNdx=u+zXNdX. El cierre hacia abajo de un conjuntoX es el conjuntoX de los vectores{vNdxx .{vNdxX.xv}XX.{vNdxx.vx}

Tenga en cuenta que si para un conjunto finito B de N d y si T es una red de Petri, podemos calcular una nueva red de Petri T B de manera que para cada configuración x , y , tengamos x Ty y x , yU si, y solo si, x T ByU=BBNdTTBx,yxTyx,yUxTByt=(u,v)bBtb=(u+z,v+z)zNd1idTU ={tbtTz(i)=max{b(i)u(i),b(i)v(i),0}1idTU={tbtTbB} cumple el requisito.

Ahora, suponga que es una red de Petri, el conjunto de obstáculos. Introducimos el conjunto finito . Observe que podemos calcular efectivamente un conjunto finito de tal que . Sea la relación binaria definida sobre por if , o existe tal queO D = O B N d B = N dD R N dO x R y x = y x , yN dO x TxT TOD=OBNdB=NdDRNdOxRyx=yx,yNdOxTxTByTy.

Ahora, solo observe que si existe una ejecución desde la configuración inicial hasta la final que evita el obstáculo , entonces existe una que evita el obstáculo en y eso pasa por configuraciones en como máximo el cardenal de ese conjunto. Por lo tanto, el problema se reduce a seleccionar configuraciones distintas no deterministas in , corregir como la configuración inicial , como la final , y verifique quey O O DO c 1,,c nDO c 0x cn+1y c jRc j+1jxyOODOc1,,cnDOc0xcn+1ycjRcj+1 por cada . Este último problema se reduce a las preguntas clásicas de accesibilidad para las redes de Petri.j

Jérôme
fuente
Genial, muchas gracias !! ¡Esta pregunta volvía a mi mente periódicamente!
Nicolas Perrin
2
Ahora, puede ser obvio, pero me gustaría hacer una pregunta de seguimiento, para estar seguro. ¿Qué sucede si permitimos que sea ​​el conjunto de marcas? En ese caso, la misma construcción exacta no funciona. ¿Existe un argumento simple que extienda el resultado? Zd
Nicolas Perrin
4

He estado pensando en su pregunta para los sistemas de adición de vectores con estados (VASS) que son equivalentes a VAS y se me ocurrió esta solución. Ahora, he leído la buena respuesta de Jérôme y tengo que decir que mi respuesta es muy similar, así que acepte su respuesta incluso si considera que la mía es correcta.


Idea: es posible convertir un VASS en un VASS que prohíbe vectores más pequeños o iguales a los obstáculos. Esto no es exactamente lo que queremos, ya que se permite alcanzar vectores más pequeños pero no iguales a los obstáculos. Sin embargo, hay finitamente muchos de esos vectores. Esto permite una descomposición de ejecuciones mínimas en muchas ejecuciones que son una transición de o una ejecución equivalente de . Por lo tanto, , el problema es decidible.V V V VVVV


Detalles: Let ser un -VASS, es decir, es un gráfico marcado finito tal que . Deje que sea ​​el conjunto de obstáculos. Deje y , escribimos siempre que sea ​​un ejecutar de para con cada configuración intermedia en . Denotamosd V T Q × Z d × Q O N p ( u ) π X q ( v )V=(Q,T)dVTQ×Zd×Q pi T * X N dONdπ­TXNdp(u)πXq(v)πp(u)q(v)Q×XX={y:yx for some xX} .

Sea una ejecución mínima tal que , es decir, una ejecución mínima que evita los obstáculos Luego, según el principio del casillero, se puede factorizar como una carrera que ingresa solo finitamente muchas veces. Más formalmente, existen , y tal queπp(u)πNdOq(v)πOOt1,t1,tn+1,tn+1T{ε}π1,,πn+1T{pi(ui),qi(vi),ri(wi)}i[0,n+1]Q×Nd

  • π=t1π1t1tn+1πn+1tn+1 ,
  • i[0,n] pi(ui)ti+1Ndqi+1(vi+1)πi+1NdOri+1(wi+1)ti+1Ndpi+1(ui+1)
  • p0(u0)=p(u), pn+1(un+1)=q(v) ,
  • i[1,n] uiOO .
  • n|Q||O|.

Por lo tanto, es suficiente adivinar , y las configuraciones intermedias. Prueba de si se puede llevar a cabo convirtiendo en un nuevo -VASS donde cada transición se reemplaza por un gadget de transiciones. Por ejemplo, si , las transiciones se reemplazan de la siguiente manera:nt1,t1,,tn+1,tn+1p(x)NdOq(y)VdVtT4|O|+1O={(1,5),(2,3)}VASS gadget

Michael Blondin
fuente
1
¡¡Gracias!! Dos respuestas correctas en menos de 2 días, tengo que decir que esta comunidad funciona bien :)
Nicolas Perrin