Parallel Communicating Finite Automata: Productiveness and Succinctness

Parallel Communicating Finite Automata (PCFA) extend classical finite automata by enabling multiple automata to operate in parallel and communicate upon request, capturing essential aspects of parallel and distributed computation. This model is relevant for studying complex systems such as computer networks and multi-agent environments. In this paper, we explore two key aspects of PCFA: their undecidability and their descriptional complexity. We first show that deterministic PCFA of degree 2 (DPCFA(2)) can accept a set of valid computations of a deterministic Turing machine, leading to the undecidability of restricted versions of emptiness and universality problems. Additionally, we employ the concept of productiveness (a stronger form of non-recursive enumerability) to demonstrate that these problems are not only undecidable but also unprovable. Second, we investigate the descriptional complexity of PCFA and establish non-recursive trade-offs between different PCFA models and many classes of language descriptors, such as DFAs and subclasses of regular expressions, offering new insights into their computational and structural properties.