State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
Publication:5896095
DOI10.1007/978-3-319-94631-3_20zbMath1435.68118arXiv1811.06336MaRDI QIDQ5896095
Publication date: 30 June 2020
Published in: Theoretical Computer Science, Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.06336
state complexity; alternating finite automata; directed graph connectivity problem; linear space hypothesis; parameterized decision problems; polynomial-size advice; sub-linear-space computability
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
05C20: Directed graphs (digraphs), tournaments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
05C40: Connectivity
68Q27: Parameterized complexity, tractability and kernelization
