Timeline for Finding maximal factorization of regular languages
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15, 2013 at 15:20 | vote | accept | Laura | ||
| S Aug 13, 2013 at 8:51 | history | bounty ended | Raphael | ||
| S Aug 13, 2013 at 8:51 | history | notice removed | Raphael | ||
| S Aug 12, 2013 at 7:32 | history | bounty started | Raphael | ||
| S Aug 12, 2013 at 7:32 | history | notice added | Raphael | Reward existing answer | |
| Aug 11, 2013 at 20:23 | answer | added | Cornelius Brand | timeline score: 8 | |
| Aug 10, 2013 at 18:53 | comment | added | D.W.♦ | @Raphael, it looks to me like $v$ is valid. Letting $X=\Sigma^* a \Sigma^*$, $Y=\Sigma^* b \Sigma^*$, $(X,Y)$ is a factorization, since $X \cdot Y = {\cal L}$ (consider any string that contains an $a$, then any sequence of $a$'s and/or $b$'s, then eventually a $b$: this string must have some point where the first $b$ appears, so that is a point where it contains $ab$). I don't have a proof that it is maximal, but I can't find any larger sets $X',Y'$ that are a factorization of ${\cal L}$. | |
| Aug 10, 2013 at 18:28 | history | edited | D.W.♦ | CC BY-SA 3.0 |
fix latex typo
|
| Aug 10, 2013 at 18:21 | comment | added | D.W.♦ | Laura, I don't know how to solve the problem. That said, I'm still not sure I understand. Are you saying: the goal is to find all of the maximal pairs? If so, is it known that there cannot be exponentially many maximal pairs? Also, what do you mean when you say the pairs are unique? It seems like you have already given a counter-example: a language ${\cal L}$ that has more than one maximal pair. | |
| Aug 7, 2013 at 15:19 | comment | added | vzn | have not studied this question closely but as far as decomposing FSMs, there is the krohn-rhodes decomposition that decomposes them into a "wreath product" or "cascade" that may be relevant or applicable in some way. | |
| Aug 7, 2013 at 12:12 | history | edited | Laura | CC BY-SA 3.0 |
added 311 characters in body
|
| Aug 7, 2013 at 12:04 | comment | added | Laura | The example is taken from the paper mentioned above. $u,v,w$ are supposed to be maximal pairs. I also do not understand how $v$ is computed since it seems not necessarily be in $\mathcal{L}$. I will post another example. | |
| Aug 7, 2013 at 11:49 | comment | added | Raphael | I don't understand your examples. Are $u,v,w$ supposed to be all maximal pairs? $v$ does not seem to be valid... | |
| Aug 7, 2013 at 9:41 | comment | added | Laura | I agree, that it doesn't make sense to enumerate all pairs by an algorithm and then find the maximal pairs. But I have no idea on how to proceed finding those pairs. I checked weather various accepted words have the same past and future in an automaton to somehow find a classification of words. But this does not give me all pairs and not always maximal pairs. | |
| Aug 7, 2013 at 9:32 | history | edited | Laura | CC BY-SA 3.0 |
added 257 characters in body
|
| Aug 7, 2013 at 9:25 | comment | added | Laura | The language is given by a finite automata or a regex. Then, we try to find the maximal pairs of sets of words (represented by regex as well) holding the above properties. These pairs should be unique (if I understood that correctly, otherwise there is a contradiction towards the maximality criterion). Due to maximality, the set is finite. We can also use $\mathcal{L} $ itself in the regex. Better? | |
| Aug 7, 2013 at 5:12 | comment | added | D.W.♦ | I wonder if you might want to be more specific about the problem, i.e., the last sentence of your question? Are we given $X,Y$ and we want to test whether $(X,Y)$ is maximal? Is our task to enumerate all $(X,Y)$ that are maximal? If the latter, is it clear that this list is finite or polynomial-sized? It probably doesn't make sense to ask for an algorithm to enumerate all possibilities if there are exponentially many of them. Also, do you want to specify how the language ${\cal L}$ is represented when it is presented to us, and how $X,Y$ are represented? (e.g., DFA, NFA, regexp) | |
| Aug 6, 2013 at 9:07 | history | edited | Raphael | CC BY-SA 3.0 |
edited title
|
| Aug 6, 2013 at 8:56 | history | edited | Raphael | CC BY-SA 3.0 |
edited tags
|
| Aug 5, 2013 at 20:53 | history | tweeted | twitter.com/#!/StackCompSci/status/364489234897702912 | ||
| Aug 5, 2013 at 18:04 | comment | added | Cornelius Brand | I recommend reading the following paper (esp. subsection 4.1) by Jacques Sakarovitch: perso.telecom-paristech.fr/~jsaka/PUB/Files/TUA.pdf | |
| Aug 5, 2013 at 16:12 | history | asked | Laura | CC BY-SA 3.0 |