Minimizing finite automata is computationally hard
type: Item
instance of: scholarly article
title: Minimizing finite automata is computationally hard
zbMATH Open document ID: 1071.68047
author: Andreas Malcher
published in: Theoretical Computer Science
publication date: 2005-01-11T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2126133
zbMATH Keywords: Finite automata
zbMATH Keywords: Limited nondeterminism
zbMATH Keywords: Minimization
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.03.070
OpenAlex ID: W1964127120
cites work: Q4198056
cites work: Multiple-entry finite automata
cites work: Complexity of automaton identification from given data
cites work: On measuring nondeterminism in regular languages
cites work: Q4531373
cites work: Q4045961
cites work: Q5592246
cites work: Minimal NFA Problems are Hard
cites work: Space-bounded reducibility among combinatorial problems
cites work: New problems complete for nondeterministic log space
cites work: Q4503150
cites work: Amounts of nondeterminism in finite automata
cites work: On finite automata with limited nondeterminism
cites work: Q4131648
cites work: Q4714446
DOI: 10.1016/J.TCS.2004.03.070
description: scientific article; zbMATH DE number 2126133