An intersection problem for finite automata (Q1118410)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An intersection problem for finite automata
scientific article

    Statements

    An intersection problem for finite automata (English)
    0 references
    0 references
    0 references
    1988
    0 references
    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.
    0 references
    0 references
    initial finite automata
    0 references
    intersection condition
    0 references
    combinators
    0 references
    logical relations
    0 references

    Identifiers