Name
Abstract | ||
|---|---|---|
Never minimal automata, introduced in [4], are strongly connected automata which are not minimal for any choice of their final states. In [4] the authors raise the question whether recognizing such automata is a polynomial time task or not. In this paper, we show that the complement of this problem is equivalent to the problem of checking whether or not in an edge-colored graph there is a bipartite subgraph whose edges are colored using all the colors. We prove that this graph theoretic problem is NP-complete, showing that checking the property of never-minimality is unlikely a polynomial time task. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22321-1_32 | Developments in Language Theory |
Keywords | Field | DocType |
rainbow bipartite subgraph problem,bipartite subgraph,graph theoretic problem,polynomial time task,final state,minimal automaton,edge-colored graph | Discrete mathematics,Equivalence relation,Combinatorics,Computer science,Bipartite graph,Automaton,Induced subgraph isomorphism problem,Time complexity,Strongly connected component,Rainbow,Subgraph isomorphism problem | Conference |
Citations | PageRank | References |
3 | 0.52 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Emanuele Rodaro | 1 | 55 | 15.63 |
| Pedro V. Silva | 2 | 141 | 29.42 |