On the computational complexity of problems related to distinguishability sets
type: Item
instance of: scholarly article
title: On the computational complexity of problems related to distinguishability sets
zbMATH Open document ID: 1390.68396
author: Markus Holzer
author: Sebastian Jakobi
published in: Information and Computation
publication date: 2018-03-21T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6851689
zbMATH Keywords: distinguishability sets
zbMATH Keywords: synchronization
zbMATH Keywords: computational complexity
zbMATH Keywords: state complexity
zbMATH Keywords: deterministic finite automata
MaRDI profile type: MaRDI publication profile
full work available at URL: j.ic.2017.09.003
OpenAlex ID: W2751846635
cites work: Distinguishability Operations and Closures
cites work: Descriptional and computational complexity of finite automata -- a survey
cites work: Synchronizing Automata and the Černý Conjecture
cites work: Q4198075
cites work: Minimal NFA Problems are Hard
cites work: Q3707407
cites work: The parallel complexity of finite-state automata problems
cites work: Nondeterministic Space is Closed under Complementation
cites work: The method of forced enumeration for nondeterministic automata
cites work: Space-bounded reducibility among combinatorial problems
cites work: On a complexity hierarchy between L and NL
DOI: 10.1016/J.IC.2017.09.003
description: scientific article; zbMATH DE number 6851689