Remarks on separating words
Proceedings of the 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011.
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin/Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73455 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| _version_ | 1811088245123973120 |
|---|---|
| author | Demaine, Erik D. Eisenstat, Sarah Charmian Shallit, Jeffrey Wilson, David A. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Eisenstat, Sarah Charmian Shallit, Jeffrey Wilson, David A. |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | Proceedings of the 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. |
| first_indexed | 2024-09-23T13:58:42Z |
| format | Article |
| id | mit-1721.1/73455 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:58:42Z |
| publishDate | 2012 |
| publisher | Springer Berlin/Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/734552022-09-28T17:30:00Z Remarks on separating words Demaine, Erik D. Eisenstat, Sarah Charmian Shallit, Jeffrey Wilson, David A. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Eisenstat, Sarah Charmian Wilson, David A. Proceedings of the 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length ≤ n (by accepting one and rejecting the other). In this paper we survey what is known and unknown about the problem, consider some variations, and prove several new results. 2012-09-27T21:33:19Z 2012-09-27T21:33:19Z 2011-07 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-22599-4 http://hdl.handle.net/1721.1/73455 Demaine, Erik D. et al. “Remarks on Separating Words.” Descriptional Complexity of Formal Systems. Ed. Markus Holzer, Martin Kutrib, & Giovanni Pighizzini. LNCS Vol. 6808. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 147-157. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 en_US http://dx.doi.org/ 10.1007/978-3-642-22600-7_12 Descriptional Complexity of Formal Systems Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin/Heidelberg MIT web domain |
| spellingShingle | Demaine, Erik D. Eisenstat, Sarah Charmian Shallit, Jeffrey Wilson, David A. Remarks on separating words |
| title | Remarks on separating words |
| title_full | Remarks on separating words |
| title_fullStr | Remarks on separating words |
| title_full_unstemmed | Remarks on separating words |
| title_short | Remarks on separating words |
| title_sort | remarks on separating words |
| url | http://hdl.handle.net/1721.1/73455 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| work_keys_str_mv | AT demaineerikd remarksonseparatingwords AT eisenstatsarahcharmian remarksonseparatingwords AT shallitjeffrey remarksonseparatingwords AT wilsondavida remarksonseparatingwords |