The Recursive Arrival Problem

Thomas Webster

doi:10.4204/EPTCS.390.11

The Recursive Arrival Problem

Thomas Webster

School of Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study an extension of the Arrival problem, called Recursive Arrival, inspired by Recursive State Machines, which allows for a family of switching graphs that can call each other in a recursive way. We study the computational complexity of deciding whether a Recursive Arrival instance terminates at a given target vertex. We show this problem is contained in NP∩coNP, and we show that a search version of the problem lies in UEOPL, and hence in EOPL = PLS∩PPAD. Furthermore,we show P-hardness of the Recursive Arrival decision problem. By contrast, the current best-known hardness result for Arrival is PL-hardness.

Original language	English
Title of host publication	Proceedings of the 14th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2023
Publisher	Open Publishing Association
Pages	168–184
Number of pages	16
Volume	390
DOIs	https://doi.org/10.4204/EPTCS.390.11
Publication status	Published - 30 Sept 2023
Event	Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification - Udine, Italy Duration: 18 Sept 2023 → 20 Sept 2023 Conference number: 14 https://gandalf23.uniud.it/

Publication series

Name	Electronic Proceedings in Theoretical Computer Science
ISSN (Electronic)	2075-2180

Conference

Conference	Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification
Abbreviated title	GandALF 2023
Country/Territory	Italy
City	Udine
Period	18/09/23 → 20/09/23
Internet address	https://gandalf23.uniud.it/

Access to Document

10.4204/EPTCS.390.11Licence: Creative Commons: Attribution (CC-BY)

Recursive Arrival_WEBSTER_DOA07082023_AFVAccepted author manuscript, 493 KBLicence: Creative Commons: Attribution (CC-BY)
The recursive arrival_WEBSTER_DOA07082023_VOR_CC BYFinal published version, 392 KBLicence: Creative Commons: Attribution (CC-BY)

https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?GandALF2023.11Licence: Creative Commons: Attribution (CC-BY)

Cite this

@inproceedings{31d7f3e209da43979bb68b26d9b034b9,

title = "The Recursive Arrival Problem",

abstract = "We study an extension of the Arrival problem, called Recursive Arrival, inspired by Recursive State Machines, which allows for a family of switching graphs that can call each other in a recursive way. We study the computational complexity of deciding whether a Recursive Arrival instance terminates at a given target vertex. We show this problem is contained in NP∩coNP, and we show that a search version of the problem lies in UEOPL, and hence in EOPL = PLS∩PPAD. Furthermore,we show P-hardness of the Recursive Arrival decision problem. By contrast, the current best-known hardness result for Arrival is PL-hardness.",

author = "Thomas Webster",

note = "Publisher Copyright: {\textcopyright} T. Webster.; Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2023 ; Conference date: 18-09-2023 Through 20-09-2023",

year = "2023",

month = sep,

day = "30",

doi = "10.4204/EPTCS.390.11",

language = "English",

volume = "390",

series = "Electronic Proceedings in Theoretical Computer Science",

publisher = "Open Publishing Association",

pages = "168–184",

booktitle = "Proceedings of the 14th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2023",

address = "Australia",

url = "https://gandalf23.uniud.it/",

}

Webster, T 2023, The Recursive Arrival Problem. in Proceedings of the 14th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2023. vol. 390, Electronic Proceedings in Theoretical Computer Science, Open Publishing Association, pp. 168–184, Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification, Udine, Italy, 18/09/23. https://doi.org/10.4204/EPTCS.390.11

TY - GEN

T1 - The Recursive Arrival Problem

AU - Webster, Thomas

N1 - Conference code: 14

PY - 2023/9/30

Y1 - 2023/9/30

N2 - We study an extension of the Arrival problem, called Recursive Arrival, inspired by Recursive State Machines, which allows for a family of switching graphs that can call each other in a recursive way. We study the computational complexity of deciding whether a Recursive Arrival instance terminates at a given target vertex. We show this problem is contained in NP∩coNP, and we show that a search version of the problem lies in UEOPL, and hence in EOPL = PLS∩PPAD. Furthermore,we show P-hardness of the Recursive Arrival decision problem. By contrast, the current best-known hardness result for Arrival is PL-hardness.

AB - We study an extension of the Arrival problem, called Recursive Arrival, inspired by Recursive State Machines, which allows for a family of switching graphs that can call each other in a recursive way. We study the computational complexity of deciding whether a Recursive Arrival instance terminates at a given target vertex. We show this problem is contained in NP∩coNP, and we show that a search version of the problem lies in UEOPL, and hence in EOPL = PLS∩PPAD. Furthermore,we show P-hardness of the Recursive Arrival decision problem. By contrast, the current best-known hardness result for Arrival is PL-hardness.

U2 - 10.4204/EPTCS.390.11

DO - 10.4204/EPTCS.390.11

M3 - Conference contribution

VL - 390

T3 - Electronic Proceedings in Theoretical Computer Science

SP - 168

EP - 184

BT - Proceedings of the 14th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2023

PB - Open Publishing Association

T2 - Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification

Y2 - 18 September 2023 through 20 September 2023

ER -

The Recursive Arrival Problem

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this