Given a family of recognizable languages L1, . . . ,Lm and recognizable languages K1 ⊆ K2, the relative inclusion star height problem means to compute the minimal star height of some rational expression r over L1, . . . ,Lm satisfying K1 ⊆ L(r) ⊆ K2. We show that this problem is of elementary complexity and give a detailed analysis its complexity depending on the representation of K1 and K2 and whether L1, . . . ,Lm are singletons.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:33092 |
| Date | 06 February 2019 |
| Creators | Kirsten, Daniel |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:article, info:eu-repo/semantics/article, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 0973-6999 |
Page generated in 0.0088 seconds