OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Expressive Equivalence and Succinctness of Parametrized Automata with Respect to Finite Memory Automata

Jha, Tushant and Belkhir, Walid and Chevalier, Yannick and Rusinowitch, Michaël Expressive Equivalence and Succinctness of Parametrized Automata with Respect to Finite Memory Automata. (2016) In: International Conference on Service Oriented Computing (ICSOC 2015), 16 November 2015 - 19 November 2015 (Goa, India).

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
388kB

Official URL: https://doi.org/10.1007/978-3-662-50539-7_12

Abstract

We compare parametrized automata, a class of automata recently introduced by the authors, against finite memory automata with non-deterministic assignment, an existing class of automata used to model services. We prove that both classes have the same expressive power, while parametrized automata can be exponentially succinct in some cases. We then prove that deciding simulation preorder for parametrized automata is EXPTIME-complete, extending an earlier result showing it in EXPTIME.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in Volume 9586 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN: 978-3-662-50538-0 The original PDF is available at: https://link.springer.com/chapter/10.1007/978-3-662-50539-7_12
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (FRANCE)
French research institutions > Institut National de la Recherche en Informatique et en Automatique - INRIA (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Statistics:download
Deposited By: IRIT IRIT
Deposited On:17 Apr 2019 14:25

Repository Staff Only: item control page