scientific article; zbMATH DE number 2040922

MaRDI QIDQ4452078zbMATHFDO

Authors Andreas Malcher

Publication date 11 February 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2710/27100386.htm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Minimizing finite automata is computationally hard
• scientific article; zbMATH DE number 6300100
• scientific article; zbMATH DE number 4166871
• scientific article; zbMATH DE number 4108165
• Minimisation of automata
• The minimization of a kind of non-deterministic finite automata
• scientific article; zbMATH DE number 4108164
• Minimal NFA Problems are Hard
• scientific article; zbMATH DE number 176769
• Minimization of lattice automata

Cited in

(10)

• String execution time for finite languages: max is easy, min is hard
• Minimal NFA Problems are Hard
• A graph theoretic approach to automata minimality
• Minimizing finite automata is computationally hard
• The Tractability Frontier for NFA Minimization
• scientific article; zbMATH DE number 176769 (Why is no real title available?)
• scientific article; zbMATH DE number 6300100 (Why is no real title available?)
• A maxmin problem on finite automata
• scientific article; zbMATH DE number 4108165 (Why is no real title available?)
• Compression of finite-state automata through failure transitions

This page was built for publication:

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