Never minimal automata and the rainbow bipartite subgraph problem

• Type: Article in International Conference Proceedings Book
• Date: 2011

Authors

Emanuele Rodaro (Author) FCUP; Pedro V. Silva (Author) FCUP

Conference proceedings International

Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Pages: 374-385

15th International Conference on Developments in Language Theory, DLT 2011

Milan, 19 July 2011 through 22 July 2011

Indexing

Scopus - 3 Citations

Other information

Authenticus ID: P-007-ZDZ

DOI: 10.1007/978-3-642-22321-1_32

Abstract (EN): 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. © 2011 Springer-Verlag.

Language: English

Type (Professor's evaluation): Scientific