IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v13y2025i8p1265-d1633100.html
   My bibliography  Save this article

Parallel Communicating Finite Automata: Productiveness and Succinctness

Author

Listed:
  • 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)

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.

Suggested Citation

  • Jingnan Xie & Ching-Sheng Lin & Harry B. Hunt, 2025. "Parallel Communicating Finite Automata: Productiveness and Succinctness," Mathematics, MDPI, vol. 13(8), pages 1-13, April.
    • Handle: RePEc:gam:jmathe:v:13:y:2025:i:8:p:1265-:d:1633100
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/13/8/1265/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/13/8/1265/
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:13:y:2025:i:8:p:1265-:d:1633100. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.