Timeline for decidability of regularity of a language depending on representation
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2020 at 7:16 | answer | added | J.-E. Pin | timeline score: 1 | |
| May 16, 2019 at 14:04 | comment | added | Benjamin Steinberg | Rice’s theorem covers the Turing machine. | |
| May 16, 2019 at 13:41 | comment | added | Sebastian Mueller | In light of Benjamin's answer, for both of the definitions I gave it is not possible to decide regularity. So let's settle on the language given as a set of words defined by some weak first-order or propositional formula (possibly over some parameter). | |
| May 16, 2019 at 13:19 | comment | added | Sebastian Mueller | @Benjamin. Thanks, is that obvious or can you point to some literature? | |
| May 16, 2019 at 13:14 | comment | added | Sebastian Mueller | @ Andreas. I didn't want to specify this, as I wanted to know the answer for several different representations, if possible. So let's assume the set is given by a black-box deciding membership (I guess that would mean you have $L$ as an oracle, if you want to check membership with a Turing machine). Also, what if the set was defined by some formula $\varphi$ in some logic (with or without parameters). For example, if $\varphi$ was some expression in first-order logic over $\mathbb{N}$. I know it is a very general question... I'm also happy if I am pointed towards some literature or papers. | |
| May 16, 2019 at 13:01 | comment | added | Andreas Blass | What do you mean by "presented with a set"? Are you just given a black box for deciding membership in the set? Or an algorithm fo deciding membership? Or an algorithm that lists the members of the set? Or what? | |
| May 16, 2019 at 13:00 | review | Suggested edits | |||
| May 16, 2019 at 13:25 | |||||
| May 16, 2019 at 12:58 | comment | added | Benjamin Steinberg | If you give a language by a Turing machine you cannot decide if it is regular, so these things of course depend on the representation. I would guess you would need to be more specific about what sorts of representations you allow in order to get a precise answer. | |
| May 16, 2019 at 12:44 | history | asked | Sebastian Mueller | CC BY-SA 4.0 |