An automaton over data words that captures EMSO logic

Details An automaton over data words that captures EMSO logic An automaton over data words that captures EMSO logic

2011-01-24

arxiv.org/abs/1101.4475v4

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.1007/978-3-642-23217-6_12

We develop a general framework for the specification and implementation of systems whose executions are words, or partial orders, over an infinite alphabet. As a model of an implementation, we introduce class register automata, a one-way automata model over words with multiple data values. Our model combines register automata and class memory automata. It has natural interpretations. In particular, it captures communicating automata with an unbounded number of processes, whose semantics can be described as a set of (dynamic) message sequence charts. On the specification side, we provide a local existential monadic second-order logic that does not impose any restriction on the number of variables. We study the realizability problem and show that every formula from that logic can be effectively, and in elementary time, translated into an equivalent class register automaton.

Affiliated with

Also associated with

No associations

Rating

An automaton over data words that captures EMSO logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An automaton over data words that captures EMSO logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An automaton over data words that captures EMSO logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636465