Better Algorithms for Analyzing and Enacting Declarative Workflows using LTL

This post has 239 words. Reading it will take approximately 1 minute.

GD Star Rating
loading...

This is a presentation of the paper

M. Westergaard, “Better Algorithms for Analyzing and Enacting Declarative Workflow Languages Using LTL,” in Business Process Management, 2011, pp. 83-98.
[Bibtex]

@inproceedings{improved-translation,
author = {Westergaard, Michael},
affiliation = {Department of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands},
title = {Better Algorithms for Analyzing and Enacting Declarative Workflow Languages Using LTL},
booktitle = {Business Process Management},
series = {Lecture Notes in Computer Science},
editor = {Rinderle-Ma, Stefanie and Toumani, Farouk and Wolf, Karsten},
publisher = {Springer Berlin / Heidelberg},
isbn = {978-3-642-23058-5},
keyword = {Computer Science},
pages = {83-98},
volume = {6896},
url = {http://dx.doi.org/10.1007/978-3-642-23059-2_10},
doi = {10.1007/978-3-642-23059-2_10},
note = {10.1007/978-3-642-23059-2_10},
abstract = {Declarative workflow languages are easy for humans to understand and use for specifications, but difficult for computers to check for consistency and use for enactment. Therefore, declarative languages need to be translated to something a computer can handle. One approach is to translate the declarative language to linear temporal logic (LTL), which can be translated to finite automata. While computers are very good at handling finite automata, the translation itself is often a road block as it may take time exponential in the size of the input. Here, we present algorithms for doing this translation much more efficiently (around a factor of 10,000 times faster and handling 10 times larger systems on a standard computer), making declarative specifications scale to realistic settings.},
year = {2011}
}

i gave at BPM 2011.

2 Comments on "Better Algorithms for Analyzing and Enacting Declarative Workflows using LTL"

Trackback | Comments RSS Feed

Twan says:

July 7, 2012 at 00:11

GD Star Rating
loading...
Your approach reminds me of the Karatsuba multiplication algorithm.

- Michael says:
  
  July 10, 2012 at 12:42
  
  GD Star Rating
  loading...
  Heh, I never thought of it like that, though I agree there is a connection in the whole looking at a seemingly opaque problem and applying a trick to be able to use divide and conquer. It would be interesting to look into whether similar tricks used in Karatsuba multiplication could be used in automaton multiplication…