Toggle Main Menu Toggle Search

ePrints

An efficient characterization of petri net solvable binary words

Lookup NU author(s): Professor Maciej Koutny, Dr Lukasz Mikulski

Downloads

Full text for this publication is not currently held within this repository. Alternative links are provided below where available.


Abstract

© 2018, Springer International Publishing AG, part of Springer Nature.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 xk, 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.


Publication metadata

Author(s): de Frutos Escrig D, Koutny M, Mikulski L

Editor(s): Victor Khomenko and Olivier H. Roux

Publication type: Conference Proceedings (inc. Abstract)

Publication status: Published

Conference Name: 39th International Conference on Applications and Theory of Petri Nets and Concurrency (PETRI NETS 2018)

Year of Conference: 2018

Pages: 207-226

Online publication date: 08/05/2018

Acceptance date: 02/04/2018

ISSN: 0302-9743

Publisher: Springer Verlag

URL: https://doi.org/10.1007/978-3-319-91268-4_11

DOI: 10.1007/978-3-319-91268-4_11

Library holdings: Search Newcastle University Library for this item

Series Title: Lecture Notes in Computer Science

ISBN: 9783319912677


Actions

    Link to this publication


Share