Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation
| Autor: | Juraj Šebej, Matúš Palmovský, Jozef Jirásek |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
010102 general mathematics
0102 computer and information sciences Star (graph theory) 01 natural sciences Prefix Complementation Combinatorics 010201 computation theory & mathematics Factor (programming language) Computer Science (miscellaneous) 0101 mathematics Suffix computer Mathematics computer.programming_language |
| Zdroj: | International Journal of Foundations of Computer Science. 30:1091-1115 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054119400306 |
| Popis: | We study Kuratowski algebras generated by prefix-, suffix-, factor-, and subword-free languages under the operations of star and complementation. We examine 12 possible algebras, and for each of them, we decide whether or not it can be generated by a prefix-, suffix-, factor-, or subword-free language. In each case when an algebra can be generated by such a language, we show that this language can be taken to be regular, and we compute upper bounds on the state complexities of all the generated languages. Finally, we find generators that maximize these complexities. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|