An intersection problem for finite automata (Q1118410): Difference between revisions

Let M(A,S) be the set of all initial finite automata with state space S of k states and alphabet A of n letters and f: M(A,S)\(\to S\). The language accepted by \(M\in M(A,S)\) and f is the set of words in A mapping the initial state of M to f(M). A map f satisfies the m-intersection condition if for any m machines in M(A,S) there is a word accepted by all of them. Let m(n,k) be the minimum m such that for any f satisfying the m-intersection condition there is a word which belongs to all the languages accepted by M(A,S) and f. The authors show that m(n,k)\(\geq 3\) for n,k\(\geq 2\) and \(m(2,k)=3\), and give some other partial results. The problem is close to a question by Plotkin concerning the connection between combinators and logical relations.