Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Finite Automata with Colored Accepting States and Their Unmixedness Problems Automata Terhad dengan Keadaan Penerima Berwarna dan Masalah Tidak Bercampurnya

Yoshiaki TAKAHASHI, Akira ITO

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Beberapa buku teks bahasa formal dan teori automata secara tersirat menyatakan kesamaan struktur binari n-graf de Bruijn berdimensi dan gambar rajah keadaan automata terhingga penentu keadaan minimum yang menerima bahasa biasa (0+1)*1(0+1)n-1. Dengan memperkenalkan automata terhingga khas yang keadaan penerimaannya diperhalusi dengan dua atau lebih warna, kami memanjangkan fakta ini kepada kedua-duanya kversi -ary. Maksudnya, kita buktikan k-sampai n-graf de Brujin dimensi dan rajah keadaan untuk automata terhingga berwarna deterministik keadaan minimum yang menerima (k-1)-tuple bahasa biasa (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,dan(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 adalah isomorfik untuk sewenang-wenangnya k lebih daripada atau sama dengan 2. Kami juga menyiasat sifat automata terhingga berwarna itu sendiri dan memberikan keputusan kerumitan pengiraan pada tiga masalah keputusan mengenai ketidakcampuran warna bagi yang tidak tentu.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.491-502
Tarikh penerbitan
2022/03/01
Diumumkan
2021/11/01
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2021FCP0012
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
kategori

Pengarang

Yoshiaki TAKAHASHI
  Oshima College
Akira ITO
  Yamaguchi University

Kata kunci

Contents [show]