An Efficient Characterization of Petri Net Solvable Binary Words





Publicado en

Actas de las XVIII Jornadas de Programación y Lenguajes (PROLE 2018)

Licencia Creative Commons


We present a simple characterization of the set of Petri net solvable binary words. It states that they are exactly the extensions of the prefixes of Petri net cyclic solvable words, by some prefix x^k, where x is any letter of the binary alphabet being considered, and k is any natural number. We derive several consequences of this characterization which, in a way, shows that the set of solvable words is smaller than expected. Therefore, the existing conjecture that all of them can be generated by quite simple net is not only confirmed, but indeed reinforced. As a byproduct of the characterization, we also present a linear time algorithm for deciding whether a binary word is solvable. The key idea is that the connection with the cyclic solvable words induces certain structural regularity. Therefore, one just needs to look for possible irregularities, which can be done in a structural way, resulting in a rather surprising linearity of the decision algorithm. Finally, we employ the obtained results to provide a characterization of reversible binary transition systems. Artículo aceptado para su presentación en Petri Nets 2018 - The 39th International Conference on Applications and Theory of Petri Nets and Concurrency. Bratislava, Slovakia, June 24-29, 2018. Los "proceedings" serán publicados en el Volumen 10877 de la serie LNCS de Springer.


Acerca de de Frutos Escrig, David

Palabras clave

Binary Transition Systems, Binary Words, Petri Nets, Reversibility, Word Solvability
Página completa del ítem
Notificar un error en este resumen
Mostrar cita
Mostrar cita en BibTeX
Descargar cita en BibTeX