State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis

DOI10.1007/978-3-319-94631-3_20zbMath1435.68118arXiv1811.06336OpenAlexW2850503404MaRDI QIDQ5896095

Tomoyuki Yamakami

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

zbMATH Keywords

state complexityalternating finite automatadirected graph connectivity problemlinear space hypothesisparameterized decision problemspolynomial-size advicesub-linear-space computability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ How does adiabatic quantum computation fit into quantum automata theory? ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two-way automata making choices only at the endmarkers
• Two-way unary automata versus logarithmic space
• Turing machines that take advice
• Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
• Two-way automata versus logarithmic space
• Two-way automata characterizations of L/poly versus NL
• Size Complexity of Two-Way Finite Automata
• Alternation
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs
• Nondeterminism and the size of two way finite automata

This page was built for publication: State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis