Parallel Communicating Finite Automata: Productiveness and Succinctness

Jingnan Xie (), Ching-Sheng Lin and Harry B. Hunt
Additional contact information
Jingnan Xie: Computer Science, Millersville University of Pennsylvania, 40 Dilworth Rd, Millersville, PA 17551, USA
Ching-Sheng Lin: Master Program of Digital Innovation, Tunghai University, Taichung City 40704, Taiwan
Harry B. Hunt: Computer Science, University at Albany, State University of New York, Albany, NY 12222, USA

Mathematics, 2025, vol. 13, issue 8, 1-13

Abstract: 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 ( D P C F A ( 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.

Keywords: parallel communicating finite automata; undecidability; productiveness; 1DFA(k); descriptional complexity (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/8/1265/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/8/1265/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:8:p:1265-:d:1633100

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().