Spelling suggestions: "subject:"desert automata"" "subject:"desert utomata""
1 |
Distance Desert Automata and Star Height SubstitutionsKirsten, Daniel 06 February 2019 (has links)
We introduce the notion of nested distance desert automata as a joint generalization and further development of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n2) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration). We also show some decidability results for some substitution problems for recognizable languages.
|
2 |
On the Complexity of the Relative Inclusion Star Height ProblemKirsten, Daniel 06 February 2019 (has links)
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.
|
Page generated in 0.0591 seconds