Hierarchies of complete problems

DOI10.1007/BF00263744MaRDI QIDQ1216952zbMATH OpenFDO

Authors Zvi Galil

Publication date 1976

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00263744

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Cited in

(22)

• An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
• The complexity of the equivalence problem for two characterizations of Presburger sets
• The complexity of decision problems for finite-turn multicounter machines
• The maximum flow problem is log space complete for P
• Iterated stack automata and complexity classes
• Problems on finite automata and the exponential time hypothesis
• Assembling molecules in ATOMIX is hard
• Decision problems and projection languages for restricted variants of two-dimensional automata
• A logic for document spanners
• A parametric analysis of the state-explosion problem in model checking
• Problems on finite automata and the exponential time hypothesis
• The complexity of intersecting finite automata having few final states
• Descriptional and Computational Complexity of Finite Automata
• The complexity of flat freeze LTL
• The emptiness problem for intersections of regular languages
• The complexity of flat freeze LTL
• Descriptional and computational complexity of finite automata -- a survey
• Computational complexity of reversible reaction systems
• Decision problems for reversible and permutation automata
• Subset mapping problems in solvable automata
• Decision problems for reversible and permutation automata
• Endmarkers can make a difference

This page was built for publication: Hierarchies of complete problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1216952)