An approximation algorithm for state minimization in 2-MDFAs

DOI10.1007/S00165-006-0005-4MaRDI QIDQ855011zbMATH OpenOpenAlexWikidataFDO

Authors C. Tauras, K. Subramani

Publication date 20 December 2006

Published in Formal Aspects of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00165-006-0005-4

zbMATH Keywords

2-MDFAFinite state automataState minimization

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• STACS 2005
• Minimizing nfa's and regular expressions
• Minimizing finite automata is computationally hard
• scientific article; zbMATH DE number 1309169
• On minimising automata with errors

Cites work

• scientific article; zbMATH DE number 176769 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Approximation algorithms for NP-hard problems.
• Minimizing finite automata is computationally hard
• On Approximate Solutions for Combinatorial Optimization Problems
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages

This page was built for publication: An approximation algorithm for state minimization in 2-MDFAs

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