?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=On+Decidability+of+Concurrent+Kleene+Algebra&rft.creator=Brunet%2C+P&rft.creator=Pous%2C+D&rft.creator=Struth%2C+G&rft.description=Concurrent+Kleene+algebras+support+equational+reasoning+about+computing+systems+with+concurrent+behaviours.+Their+natural+semantics+is+given+by+series(-parallel)+rational+pomset+languages%2C+a+standard+true+concurrency+semantics%2C+which+is+often+associated+with+processes+of+Petri+nets.+We+use+constructions+on+Petri+nets+to+provide+two+decision+procedures+for+such+pomset+languages+motivated+by+the+equational+and+the+refinement+theory+of+concurrent+Kleene+algebra.+The+contribution+to+the+first+problem+lies+in+a+much+simpler+algorithm+and+an+EXPSPACE+complexity+bound.+Decidability+of+the+second%2C+more+interesting+problem+is+new+and%2C+in+fact%2C+EXPSPACE-complete.&rft.subject=oncurrent+Kleene+algebra%2C+series-parallel+pomsets%2C+Petri+nets&rft.publisher=LIPICS&rft.contributor=Meyer%2C+R&rft.contributor=Nestmann%2C+U&rft.date=2017-08-25&rft.type=Proceedings+paper&rft.language=eng&rft.source=+++++In%3A+Meyer%2C+R+and+Nestmann%2C+U%2C+(eds.)+Proceedings+of+the+28th+International+Conference+on+Concurrency+Theory+(CONCUR+2017).++(pp.+28%3A1-28%3A15).++LIPICS%3A+Dagstuhl%2C+Germany.+(2017)+++++&rft.format=text&rft.identifier=https%3A%2F%2Fdiscovery-pp.ucl.ac.uk%2Fid%2Feprint%2F10053782%2F1%2FBrunet_On%2520decidability%2520of%2520concurrent%2520kleene%2520algebra_VoR.pdf&rft.identifier=https%3A%2F%2Fdiscovery-pp.ucl.ac.uk%2Fid%2Feprint%2F10053782%2F&rft.rights=open