Complexity of suffix-free regular languages
| Autor: | Janusz A. Brzozowski, Marek Szykuła |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Sequence
Computer Networks and Communications Semigroup Applied Mathematics Star (game theory) Concatenation Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology State (functional analysis) 01 natural sciences Theoretical Computer Science Combinatorics Computational Theory and Mathematics Regular language 010201 computation theory & mathematics Product (mathematics) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Suffix Mathematics |
| Zdroj: | FCT |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2017.05.011 |
| Popis: | A sequence \((L_k,L_{k+1} \dots )\) of regular languages in some class \({\mathcal C}\), where n is the state complexity of \(L_n\), is called a stream. A stream is most complex in class \({\mathcal C}\) if its languages together with their dialects (that is, languages that differ only very slightly from the languages in the stream) meet the state complexity bounds for boolean operations, product (concatenation), star, and reversal, have the largest syntactic semigroups, and have the maximal numbers of atoms, each of which has maximal state complexity. It is known that there exist such most complex streams in the class of regular languages, and also in the classes of right, left, and two-sided ideals. In contrast to this, we prove that there does not exist a most complex stream in the class of suffix-free regular languages. However, we do exhibit one ternary suffix-free stream that meets the bound for product and whose restrictions to binary alphabets meet the bounds for star and boolean operations. We also exhibit a quinary stream that meets the bounds for boolean operations, reversal, size of syntactic semigroup, and atom complexities. Moreover, we solve an open problem about the bound for the product of two languages of state complexities m and n in the binary case by showing that it can be met for infinitely many m and n. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect