Hierarchies of complete problems
From MaRDI portal
Publication:1216952
DOI10.1007/BF00263744zbMath0304.68044MaRDI QIDQ1216952
Publication date: 1976
Published in: Acta Informatica (Search for Journal in Brave)
Related Items
Assembling molecules in ATOMIX is hard ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ The complexity of intersecting finite automata having few final states ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Unnamed Item ⋮ The emptiness problem for intersections of regular languages ⋮ Computational complexity of reversible reaction systems ⋮ The complexity of the equivalence problem for two characterizations of Presburger sets ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ Endmarkers can make a difference ⋮ The maximum flow problem is log space complete for P ⋮ Iterated stack automata and complexity classes ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Decision problems and projection languages for restricted variants of two-dimensional automata ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ A logic for document spanners ⋮ The Complexity of Flat Freeze LTL
