Векторные системы сложения с конечными «препятствиями»

11

Система векторного сложения (VAS) - это конечный набор действий . - это набор разметок . В рабочем цикле является непустое слово маркировки й . Если такое слово существует , мы говорим , что является достижимым из .A Z d AZdN dNdm 0 m 1m nm0m1mni { 0 , , n - 1 } , m i + 1 - m iA i{0,,n1},mi+1miAm nmnм 0m0

Известно, что проблема достижимости для VAS разрешима (но ее сложность остается открытой).

Теперь предположим, что задан конечный набор запрещенных разметок ( препятствий ). Я хотел бы знать, если проблема достижимости все еще разрешима.

Интуитивно понятно, что конечный набор препятствий должен мешать трассам только локально, поэтому проблема должна оставаться разрешимой. Но это не кажется тривиальным, чтобы доказать это.

РЕДАКТИРОВАТЬ . Я сохраню ответ @ Jérôme как принятый, но я хотел бы добавить дополнительный вопрос: что, если набор меток будет ?Z dZd

Николас Перрен
источник
У вас есть хорошая рекомендация, чтобы получить представление об обоснованности доказательства? (например, слайды)
Денис
1
Вот слайды: lsv.ens-cachan.fr/Events/Pavas/slides-Leroux.pdf ; и недавняя статья: hal.archives-ouvertes.fr/hal-00674970 ; в основном достижимость решается алгоритмом перечисления, основанным на том факте, что если не достижимо из , то существуют два непересекающихся множества Пресбургера, которые каким-то образом доказывают недостижимость. Некоторые другие слайды: automata.rwth-aachen.de/movep2010/abstracts/slides-leroux.pdf . у yхx
Николя Перрен
М. Правин выступил с несколькими докладами о двух основных подходах к проблеме: cmi.ac.in/~praveenm/talks
Сильвен
Для подзадач задачи с конечными препятствиями (например, с ограниченной размерностью) кажется, что доказательство разрешимости может быть основано на свойстве «устранения зигзага». См. Этот документ: labri.fr/perso/leroux/published-papers/LS-concur04.ps и эти слайды: labri.fr/perso/sutre/Talks/Documents/… .
Николас Перрен
1
Я понимаю, почему проблема решается, когда есть ненулевые действия, которые сводятся к нулю, но что происходит, когда таких действий не существует? Часть вашего ответа была оторвана от комментария :)
Николя Перрен

Ответы:

5

Идея основана на обсуждении, которое я получил с Грегуар Сутре сегодня днем.

Проблема разрешима следующим образом.

Сеть Петри - это конечное множество пар в называемых переходами. Для заданного перехода мы обозначим через бинарное отношение, определенное на множестве конфигураций через если существует вектор такой, что и . Обозначим через одношаговое отношение достижимости . Рефлексивное и транзитивное замыкание этого отношения обозначаетсяT N d × N d t = ( u , v ) t N d x ty zN d x = u + z y = v + z Tt T tT TNd×Ndt=(u⃗ ,v⃗ )tNdx⃗ ty⃗ z⃗ Ndx⃗ =u⃗ +z⃗ y⃗ =v⃗ +z⃗ TtTtT .

Пусть будет классическим компонентно-частичным порядком над и определен если существует такой что . Закрытие вверх множества из - это множество векторов . Нисходящее замыкание множества - это множество векторов . N d ux zNdu⃗ x⃗  N d х =U +Z X N d Х {V N d |хХ .z⃗ Ndx⃗ =u⃗ +z⃗ X⃗ NdX⃗ xv }XX {vNdxx .{v⃗ Ndx⃗ X⃗ .x⃗ v⃗ }X⃗ X⃗ vx }{v⃗ Ndx⃗ x⃗ .v⃗ x⃗ }

Обратите внимание, что если для некоторого конечного множества из и если - сеть Петри, мы можем вычислить новую сеть Петри такой, что для каждой конфигурации нас есть и тогда и только тогда, когда . Фактически, если является переходом, то для каждого пусть где - вектор вU =B B NdTTBx ,y x TU⃗ =B⃗ B⃗ NdTTB⃗ x⃗ ,y⃗ y x ,yUx⃗ Ty⃗ x⃗ ,y⃗ U⃗ x T By t=(u ,v )bB tb =(x⃗ TB⃗ y⃗ t=(u⃗ ,v⃗ )b⃗ B⃗ u +z ,v +z )z Ndz (i)=max{b (i)-u (i),b (i)-v (i),0}1idTU ={ttb⃗ =(u⃗ +z⃗ ,v⃗ +z⃗ )Z⃗ Nd определяемый компонентно как для каждого . Обратите внимание, что удовлетворяет требованию.Z⃗ ( i ) = max { b⃗ (i)u⃗ (i),b⃗ (i)v⃗ (i),0}1idbtTbB }TU⃗ ={tb⃗ tTb⃗ B⃗ }

Теперь предположим, что - сеть Петри, - множество препятствий. Введем конечное множество . Заметьте, что мы можем эффективно вычислить конечный набор из такой, что . Пусть будет двоичным отношением, определенным над помощью если , или существует такой, чтоT O D = O B N d B = N dD R N dO x R y x = y x , yN dO x TxT TO⃗ D⃗ = O⃗ В⃗ NdB⃗ =NdD⃗ RNdO⃗ x⃗ Ry⃗ x⃗ =y⃗ x⃗ ,y⃗ NdO⃗ ByTyx⃗ Tx⃗ TB⃗ y⃗ Ty⃗ ,

Теперь просто обратите внимание, что если существует переход от начальной конфигурации к конечной который избегает препятствия , то существует такой, который избегает препятствия в и это проходит конфигурациями в не более чем кардинал этого набора. Следовательно, проблема сводится к выбору недетерминированных различных конфигураций в , исправьте как начальная конфигурация , как конечная , и проверьте, чтоx y O O DO c 1,,c nDO c 0x cn+1y c jRc j+1jx⃗ y⃗ O⃗ O⃗ D⃗ O⃗ c⃗ 1,,c⃗ nD⃗ O⃗ c⃗ 0x⃗ cn+1y⃗ c⃗ jRc⃗ j+1 для каждого . Эта последняя проблема сводится к классическим вопросам достижимости для сетей Петри.j

Жером
источник
Отлично, большое спасибо!! Этот вопрос периодически возвращался мне в голову!
Николя Перрен
2
Теперь, это может быть очевидно, но я бы хотел задать дополнительный вопрос, чтобы быть уверенным. Что если мы позволим быть набором меток? В этом случае точно такая же конструкция не работает. Есть ли простой аргумент, который расширяет результат? Z dZd
Николя Перрен
4

Я думал о вашем вопросе для систем сложения векторов с состояниями (VASS), которые эквивалентны VAS, и придумал это решение. Теперь я прочитал хороший ответ Жерома и должен сказать, что мой ответ очень похож, поэтому, пожалуйста, примите его ответ, даже если вы считаете мой правильный.


Идея: возможно преобразовать VASS в VASS который запрещает векторы, меньшие или равные препятствиям. Это не совсем то, что мы хотим, поскольку разрешено достигать векторов, меньших, но не равных препятствиям. Однако таких векторов конечное число. Это позволяет разложить минимумы на конечное число серий, которые являются либо переходом либо эквивалентным набором . Поэтому да , проблема разрешима.V V V V VVVV


Подробности: Пусть будет -VASS, т.е. является конечным помеченный граф таким образом, что . Пусть - множество препятствий. Пусть и , мы пишем всякий раз, когда является запускается из для с каждой промежуточной конфигурации в . Мы обозначаемV = ( Q , T ) d V T Q × Z d × QV=(Q,T)dVTQ×Zd×Q O N д л T * X N д р ( у ) л Х д ( V ) л р ( у ) д ( V ) Q × X X = { y : y ONdπ­TXNdp(u)πXq(v)πp(u)q(v)Q×Xx  для некоторого  x X }X={y:yx for some xX} .

Пусть минимальный прогон, такой что , т.е. минимальный прогон, который избегает препятствий. Тогда, по принципу голубя, может быть разложен как пробег, который входит в только конечное число раз. Более формально, существуют , и такой чтоπ p ( u ) π N dO q ( v ) π O O t 1 , t 1, t n + 1 , t n + 1T { ε } π 1 , , π n + 1T { p i ( uπp(u)πNdOq(v)π OOT1, т'1,tn+1,tn+1T{ε}π1,,πn+1Ti ) , q i ( v i ) , r i ( w i ) } i [ 0 , n + 1 ]Q × N d{pi(ui),qi(vi),ri(wi)}i[0,n+1]Q×Nd

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

Следовательно, достаточно угадать , и промежуточные конфигурации. Проверка того, можно ли путем преобразования в новый -VASS где каждый переход заменяется гаджетом из переходов. Например, если то переходы заменяются следующим образом:n t 1 , t 1 , , t n + 1 , t n + 1 p ( x ) N d O q ( y ) V d V t T 4 | O | + 1 O = { ( 1 , 5 ) , ( 2 , 3) }VASS гаджет

Майкл Блондин
источник
1
Благодаря!! Два правильных ответа менее чем за 2 дня, я должен сказать, что это сообщество работает хорошо :)
Николас Перрен