I mycket dynamiska system (t.ex. trådlösa mobila ad hoc-nätverk, robotsvärmar, fordonsnätverk osv.) Konnektivitet inte nödvändigtvis hålla vid en given tidpunkt, men temporal banor, eller resor, kan fortfarande existera över tid och rum, vilket gör databehandling möjligt; vissa av dessa system tillåter vänta (dvs. pauser vid mellanliggande noder, även kallade butik-transport framåt strategier) medan andra inte. Dessa system är naturligt modellerade som tidsvarierande grafer, där närvaron av en kant och dess latens varierar som en funktion av tiden; i dessa grafer, skillnaden mellan väntande och inte väntande motsvarar den mellan indirekta och direkta resor. Vi anser att tidsvarierande diagram är uttrycksfulla när det gäller de språk som genereras av de genomförbara resorna. Vi undersöker effekten av att vänta genom att studera skillnaden i vilken typ av språk som uttrycks genom indirekta resor (dvs. att vänta är tillåtet) och genom direkta resor (dvs. att vänta är ogenomförbart), under olika antaganden om de funktioner som styr närvaro och latens av kanter. Vi bevisar ett allmänt resultat som innebär att, om vänta är inte tillåtet, då uppsättningen av språk L nowait som kan genereras innehåller alla beräkningsbara språk när närvaron och latency funktioner är beräkningsbara. I andra änden, vi bevisar att om vänta är tillåtet, då uppsättningen av språk L väntar innehåller alla och bara vanliga språk; detta resultat, etablerat med hjälp av algebraiska egenskaper kvasi-order, innehar även om närvaron och latens är obegränsad (t.ex., eventuellt icke-komputerbara) funktioner av tid. Med andra ord, vi bevisar att, när väntan är tillåten, kraften i accepterande automaton kan sjunka drastiskt från att vara minst lika kraftfull som en Turing maskin, till att bli en Finite-State Machine. Denna stora lucka ger en inblick i effekterna av att vänta i tidsvarierande grafer. Vi studerar också avgränsad väntan, där väntan är tillåten vid en nod för högst d tid enheter, och bevisa att L vänta[d] = L nowait; det vill säga, kraften i acceptera automaton minskar endast om väntetiden är obegränsad.
Casteigts m.fl. I REF studerades tidsvägar med maximala väntetider i samband med analys av expressiviteten hos tidsgrafer.
On the expressivity of time-varying graphs
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}