{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T06:53:13Z","timestamp":1773298393319,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,7,1]],"date-time":"2016-07-01T00:00:00Z","timestamp":1467331200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2016,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Behavioral profiles have been proposed as a behavioral abstraction of dynamic systems, specifically in the context of business process modeling. A behavioral profile can be seen as a complete graph over a set of task labels, where each edge is annotated with one relation from a given set of binary behavioral relations. Since their introduction, behavioral profiles were argued to provide a convenient way for comparing pairs of process models with respect to their behavior or computing behavioral similarity between process models. Still, as of today, there is little understanding of the expressive power of behavioral profiles. Via counter-examples, several authors have shown that behavioral profiles over various sets of behavioral relations cannot distinguish certain systems up to trace equivalence, even for restricted classes of systems represented as safe workflow nets. This paper studies the expressive power of behavioral profiles from two angles. Firstly, the paper investigates the expressive power of behavioral profiles and systems captured as acyclic workflow nets. It is shown that for unlabeled acyclic workflow net systems, behavioral profiles over a simple set of behavioral relations are expressive up to configuration equivalence. When systems are labeled, this result does not hold for any of several previously proposed sets of behavioral relations. Secondly, the paper compares the expressive power of behavioral profiles and regular languages. It is shown that for any set of behavioral relations, behavioral profiles are strictly less expressive than regular languages, entailing that behavioral profiles cannot be used to decide trace equivalence of finite automata and thus Petri nets.<\/jats:p>","DOI":"10.1007\/s00165-016-0372-4","type":"journal-article","created":{"date-parts":[[2016,5,13]],"date-time":"2016-05-13T10:18:10Z","timestamp":1463134690000},"page":"597-613","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["On the expressive power of behavioral profiles"],"prefix":"10.1145","volume":"28","author":[{"given":"Artem","family":"Polyvyanyy","sequence":"first","affiliation":[{"name":"Queensland University of Technology, GPO Box 2434, 4001, Brisbane, QLD, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abel","family":"Armas-Cervantes","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Tartu, Tartu, Estonia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marlon","family":"Dumas","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Tartu, Tartu, Estonia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luciano","family":"Garc\u00eda-Ba\u00f1uelos","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Tartu, Tartu, Estonia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"crossref","unstructured":"Armas-Cervantes A. Baldan P. Dumas M. Garc\u00eda-Ba\u00f1uelos L.: Behavioral comparison of process models based on canonically reduced event structures. In: Business Process Management\u201412th International Conference BPM 2014 Haifa Israel Sep 7\u201311 2014. Proceedings vol. 8659 of Lecture Notes in Computer Science pp. 267\u2013282. Springer Berlin (2014)","DOI":"10.1007\/978-3-319-10172-9_17"},{"key":"e_1_2_1_2_2_2","doi-asserted-by":"crossref","unstructured":"Armas-Cervantes A. Baldan P. Garc\u00eda-Ba\u00f1uelos L.: Reduction of event structures under history preserving bisimulation. J. Logic. Algebraic Methods Program. (2015) (in press)","DOI":"10.1016\/j.jlamp.2015.10.004"},{"key":"e_1_2_1_2_3_2","unstructured":"Armas-Cervantes A. Dumas M. Garc\u00eda-Ba\u00f1uelos L. Polyvyanyy A.: On the suitability of generalized behavioral profiles for process model comparison. In: Web Services and Formal Methods 11th International Workshop WS-FM 2014 Eindhoven The Netherlands Sep 11\u201312 Proceedings (Accepted on 10 July 2014) (2014)"},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"crossref","unstructured":"Boudol G.: Flow event structures and flow nets. In: Semantics of Systems of Concurrent Processes LITP Spring School on Theoretical Computer Science La Roche Posay France April 23\u201327 1990 Proceedings vol. 469 of Lecture Notes in Computer Science pp. 62\u201395. Springer Berlin (1990)","DOI":"10.1007\/3-540-53479-2_4"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"crossref","unstructured":"Engelfriet J.: Determinacy \u27f6 (observation equivalence = trace equivalence). Theor. Comput. Sci. (TCS) 36 21\u201325 (1985)","DOI":"10.1016\/0304-3975(85)90028-3"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01463946"},{"key":"e_1_2_1_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.04.028"},{"key":"e_1_2_1_2_8_2","doi-asserted-by":"crossref","unstructured":"Kunze M. Weidlich M. Weske M.: Behavioral similarity: a proper metric. In: Business Process Management\u20149th International Conference BPM 2011 Clermont-Ferrand France August 30\u2013September 2 2011. Proceedings vol. 6896 of Lecture Notes in Computer Science pp. 166\u2013181. Springer Berlin (2011)","DOI":"10.1007\/978-3-642-23059-2_15"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"crossref","unstructured":"Murata T.: Petri nets: Properties analysis and applications. Proc. IEEE 77 (4) (1989)","DOI":"10.1109\/5.24143"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90112-2"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"crossref","unstructured":"Polyvyanyy A. Weidlich M. Conforti R. La Rosa M. ter Hofstede A.H.M.: The 4C spectrum of fundamental behavioral relations for concurrent systems. In: Application and Theory of Petri Nets and Concurrency\u201435th International Conference PETRI NETS 2014 Tunis Tunisia June 23\u201327 2014. Proceedings vol. 8489 of Lecture Notes in Computer Science pp. 210\u2013232. Springer New York (2014)","DOI":"10.1007\/978-3-319-07734-5_12"},{"key":"e_1_2_1_2_12_2","doi-asserted-by":"crossref","unstructured":"Polyvyanyy A. Weidlich M. Weske M.: Isotactics as a foundation for alignment and abstraction of behavioral models. In: Business Process Management\u201410th International Conference BPM 2012 Tallinn Estonia Sep 3\u20136 2012. Proceedings vol. 7481 of Lecture Notes in Computer Science pp. 335\u2013351. Springer New York (2012)","DOI":"10.1007\/978-3-642-32885-5_26"},{"key":"e_1_2_1_2_13_2","unstructured":"Sipser M.: Introduction to the Theory of Computation 3rd edn. Cengage Learning (2012)"},{"key":"e_1_2_1_2_14_2","doi-asserted-by":"crossref","unstructured":"van der Aalst W.M.P.: Verification of workflow nets. In: Application and Theory of Petri Nets 1997 18th International Conference ICATPN \u201997 Toulouse France June 23\u201327 1997 Proceedings vol. 1248 of Lecture Notes in Computer Science pp. 407\u2013426. Springer Berlin (1997)","DOI":"10.1007\/3-540-63139-9_48"},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"crossref","unstructured":"van der Aalst W.M.P.: Workflow verification: finding control-flow errors using Petri-net-based techniques. In: Business Process Management Models Techniques and Empirical Studies vol. 1806 of Lecture Notes in Computer Science pp. 161\u2013183. Springer New York (2000)","DOI":"10.1007\/3-540-45594-9_11"},{"key":"e_1_2_1_2_16_2","doi-asserted-by":"crossref","unstructured":"van Glabbeek R.J.: The Linear Time-Branching Time Spectrum vol. 458 of Lecture Notes in Computer Science. Springer New York (1990)","DOI":"10.1007\/BFb0039066"},{"key":"e_1_2_1_2_17_2","doi-asserted-by":"crossref","unstructured":"van Glabbeek R.J. Goltz U.: Equivalence notions for concurrent systems and refinement of actions. In: Mathematical Foundations of Computer Science 1989 MFCS\u201989 Porabka-Kozubnik Poland August 28\u2013Sept 1 1989 Proceedings vol. 379 of Lecture Notes in Computer Science pp. 237\u2013248. Springer New York (1989)","DOI":"10.1007\/3-540-51486-4_71"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"crossref","unstructured":"van Glabbeek R.J. Goltz U.: Refinement of actions and equivalence notions for concurrent systems. Acta Informatica (ACTA) 37 (4\/5) 229\u2013327 (2001)","DOI":"10.1007\/s002360000041"},{"key":"e_1_2_1_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90067-2"},{"key":"e_1_2_1_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2010.96"},{"key":"e_1_2_1_2_21_2","unstructured":"Weidlich M. Mendling J. Weske M.: A foundational approach for managing process variability. In: Advanced Information Systems Engineering\u201423rd International Conference CAiSE 2011 London UK June 20\u201324 2011. Proceedings vol. 6741 of Lecture Notes in Computer Science pp. 267\u2013282. Springer New York (2011)"},{"key":"e_1_2_1_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2011.04.002"},{"key":"e_1_2_1_2_23_2","doi-asserted-by":"crossref","unstructured":"Weidlich M. Polyvyanyy A. Desai N. Mendling J.: Process compliance measurement based on behavioural profiles. In: Advanced Information Systems Engineering 22nd International Conference CAiSE 2010 Hammamet Tunisia 2010. Proceedings vol. 6051 of Lecture Notes in Computer Science pp. 499\u2013514. Springer Berlin (2010)","DOI":"10.1007\/978-3-642-13094-6_38"},{"key":"e_1_2_1_2_24_2","doi-asserted-by":"crossref","unstructured":"Weidlich M. Polyvyanyy A. Mendling J. Weske M.: Efficient computation of causal behavioural profiles using structural decomposition. In: Applications and Theory of Petri Nets 31st International Conference PETRI NETS 2010 Braga Portugal June 21\u201325 2010. Proceedings vol. 6128 of Lecture Notes in Computer Science pp. 63\u201383. Springer New York (2010)","DOI":"10.1007\/978-3-642-13675-7_6"},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"crossref","unstructured":"Weidlich M. Polyvyanyy A. Mendling J. Weske M.: Causal behavioural profiles\u2014efficient computation applications and evaluation. Fundamenta Informaticae (FUIN) 113 (3\u20134) 399\u2013435 (2011)","DOI":"10.3233\/FI-2011-614"},{"key":"e_1_2_1_2_26_2","doi-asserted-by":"crossref","unstructured":"Weidlich M. Martijn J. van der Werf E.M.: On profiles and footprints-relational semantics for Petri nets. In: Application and Theory of Petri Nets\u201433rd International Conference PETRI NETS 2012 Hamburg Germany June 25\u201329 2012. Proceedings vol. 7347 of Lecture Notes in Computer Science pp. 148\u2013167. Springer Berlin (2012)","DOI":"10.1007\/978-3-642-31131-4_9"},{"key":"e_1_2_1_2_27_2","doi-asserted-by":"crossref","unstructured":"Yu S.: Regular languages. In: Rozenberg G. Salomaa A. (eds.) Handbook of Formal Languages pp. 41\u2013110. Springer Berlin Heidelberg (1997)","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-016-0372-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-016-0372-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-016-0372-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T16:08:48Z","timestamp":1641485328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-016-0372-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["10.1007\/s00165-016-0372-4"],"URL":"https:\/\/doi.org\/10.1007\/s00165-016-0372-4","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7]]}}}