The minimum consistent DFA problem cannot be approximated within any polynomial (Q4033836)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The minimum consistent DFA problem cannot be approximated within any polynomial
scientific article

    Statements

    The minimum consistent DFA problem cannot be approximated within any polynomial (English)
    0 references
    0 references
    0 references
    16 May 1993
    0 references
    reducibility and completeness
    0 references
    computations on discrete structures
    0 references
    decision problems
    0 references
    approximation algorithms
    0 references
    minimization of finite state machines
    0 references
    nonapproximability
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references