Fresh-Variable Automata: Application to Service Composition

We introduce fresh-variable automata, a natural extension of finite-state automata over infinite alphabet. In this model the transitions are labeled with constants or variables that can be refreshed in some specified states. We prove several closure properties for this class of automata and study th...

Full description

Saved in:
Bibliographic Details
Main Authors: Belkhir, Walid, Chevalier, Yannick, Rusinowitch, Michael
Format: Conference Proceeding
Language:English
Subjects:
Algorithms
Automata
Automata over infinite alphabets
Closures
Communities
Computational modeling
Computer simulation
Constants
Construction
Data models
Distance measurement
Handling
Mathematical models
Registers
service composition
simulation preorder
Web services
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce fresh-variable automata, a natural extension of finite-state automata over infinite alphabet. In this model the transitions are labeled with constants or variables that can be refreshed in some specified states. We prove several closure properties for this class of automata and study their decision problems. We show the applicability of our model in modeling Web services handling data from an infinite domain. We introduce a notion of simulation that enables us to reduce the Web service composition problem to the construction of a simulation of a target service by the asynchronous product of existing services, and prove that this construction is computable.
DOI:10.1109/SYNASC.2013.28