Name
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 systems, 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-theoretical 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.dam.2019.04.023 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Binary word,Labelled transition system,Petri net,Synthesis | Conference | 274 |
ISSN | Citations | PageRank |
0166-218X | 4 | 0.52 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evgeny Erofeev | 1 | 12 | 2.57 |
| Kamila Barylska | 2 | 29 | 5.75 |
| Łukasz Mikulski | 3 | 28 | 5.28 |
| Marcin Piatkowski | 4 | 35 | 6.79 |