Paper Info

Title | ||
---|---|---|

Parallel communicating one-way reversible finite automata system. |

Abstract | ||
---|---|---|

In this paper, we discuss the computational power of parallel communicating finite automata system with 1-way reversible finite automaton as components. We show that unlike the multi-head one way reversible finite automata model (where we are still not sure whether it accepts all the regular languages) parallel communicating one-way reversible finite automata systems can accept all the regular languages. Moreover for every multi-head one way reversible finite automaton there exist a parallel communicating one-way reversible finite automata system which accepts the same language. We also make an interesting observation that although the components of the system are reversible the system as a whole is not reversible. On the basis of which we conjecture that parallel communicating one-way reversible finite automata systems may accept languages not accepted by multi-head one way reversible finite automata. |

Year | Venue | DocType |
---|---|---|

2019 | arXiv: Formal Languages and Automata Theory | Journal |

Volume | Citations | PageRank |

abs/1903.10428 | 0 | 0.34 |

References | Authors | |

0 | 3 |

Authors (3 rows)

Cited by (0 rows)

References (0 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Debayan Ganguly | 1 | 1 | 1.03 |

Kingshuk Chatterjee | 2 | 0 | 1.01 |

Kumar Sankar Ray | 3 | 27 | 7.79 |