arXiv
Open Access
2024
Operational State Complexity of Block Languages
Guilherme Duarte
Nelma Moreira
Luca Prigioniero
Rogério Reis
Abstrak
In this paper we consider block languages, namely sets of words having the same length, and study the deterministic and nondeterministic state complexity of several operations on these languages. Being a subclass of finite languages, the upper bounds of operational state complexity known for finite languages apply for block languages as well. However, in several cases, smaller values were found. Block languages can be represented as bitmaps, which are a good tool to study their minimal finite automata and their operations, as we illustrate here.
Topik & Kata Kunci
Penulis (4)
G
Guilherme Duarte
N
Nelma Moreira
L
Luca Prigioniero
R
Rogério Reis
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2024
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓