Prague Stringology Conference 2016
Evgeny Erofeev, Kamila Barylska, Łukasz Mikulski and Marcin Piątkowski
Generating All Minimal Petri Net Unsolvable Binary Words
| Abstract: |
| Sets of finite words, as well as some infinite ones, can be described using finite systems, e.g. automata. On the other hand, some automata may be constructed with the use of even more compact models, like Petri nets. We call such automata Petri net solvable. In this paper we consider the solvability of singleton languages over a binary alphabet (i.e. binary words). An unsolvable (i.e. not solvable) word w is called minimal if each proper factor of w is solvable. We present a complete language-theory characterisation of the set of all minimal unsolvable binary words. The characterisation utilises morphic-based transformations which expose the combinatorial structure of those words, and allows to introduce a pattern matching condition for unsolvability. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |