We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
CLASS COUNTING AUTOMATA ON DATAWORDS.
- Authors
MANUEL, AMALDEV; RAMANUJAM, R.; Bournez, Oliver; Potapov, Igor
- Abstract
In the theory of automata over infinite alphabets, a central difficulty is that of finding a suitable compromise between expressiveness and algorithmic complexity. We propose an automaton model where we count the multiplicity of data values on an input word. This is particularly useful when such languages represent behaviour of systems with unboundedly many processes, where system states carry such counts as summaries. A typical recognizable language is: "every process does at most k actions labelled a". We show that emptiness is elementarily decidable, by reduction to the covering problem on Petri nets.
- Subjects
MACHINE theory; COMPUTER algorithms; COMPUTATIONAL complexity; PROGRAMMING languages; PETRI nets; DATA modeling; GRAPH labelings
- Publication
International Journal of Foundations of Computer Science, 2011, Vol 22, Issue 4, p863
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054111008465