华中科技大学学报（自然科学版）2024，Vol.52Issue(2)：42-48,7.DOI:10.13245/j.hust.240205
判定有限自动机可重置的二次多项式下界
On quadratic lower bounds for deciding resettable finite automata
摘要
Abstract
The time lower bounds of deciding resettable finite automata problem and road coloring problem were studied.It is proved that the lower bounds of these two problems are quadratic polynomials about the number of automata states and the number of vertices of directed graph,respectively.This shows that under exponential time hypothesis(ETH)the existing quadratic algorithms for both problems are almost the theoretically best.For the former problem,the fine-grained reduction from the intersection of two finite automata problem to it is established,and with transitivity of fine-grained reduction it is proved that the lower bound of determining whether the finite automaton is resettable or not is a quadratic polynomial about the number of the states.For the latter,because solving a certain problem is at least as hard as verifying one of its solutions,the proof regards deciding whether an automaton is resettable or not as verifying a solution of road coloring problem,and then it is proved that the lower bound of road coloring problem is a quadratic polynomial about the number of vertices.关键词
自动机重置判定问题/道路着色问题/细粒度复杂性/指数时间猜想/两个自动机交Key words
deciding resettable finite automata problem/road coloring problem/fine-grained complexity/exponential time hypothesis/intersection of two finite automata分类
信息技术与安全科学引用本文复制引用
朱凯,毛宜军,梁早清..判定有限自动机可重置的二次多项式下界[J].华中科技大学学报（自然科学版）,2024,52(2):42-48,7.基金项目
广东省科技计划资助项目(2020B1212060059) （2020B1212060059）
广东省农产品质量安全共性关键技术研发产业创新团队专题专家(2019-2023)项目(2019KJ130). （2019-2023）
