Abstract | ||
---|---|---|
We consider push-down automata with data (Pdad) that operate on variables ranging over the set of natural numbers. The conditions on variables are defined via gap-order constraint. Gap-order constraints allow to compare variables for equality, or to check that the gap between the values of two variables exceeds a given natural number. The messages inside the stack are equipped with values that are natural numbers reflecting their "values". When a message is pushed to the stack, its value may be defined by a variable in the program. When a message is popped, its value may be copied to a variable. Thus, we obtain a system that is infinite in two dimensions, namely we have a stack that may contain an unbounded number of messages each of which is equipped with a natural number. We present an algorithm for solving the control state reachability problem for Pdad based on two steps. We first provide a translation to the corresponding problem for context-free grammars with data (CFGD). Then, we use ideas from the framework of well quasi-orderings in order to obtain an algorithm for solving the reachability problem for CFGDS. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-40213-5_13 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
computer science | Rule-based machine translation,Natural number,Computer science,Automaton,Theoretical computer science,Ranging,Pushdown automaton,Reachability problem | Conference |
Volume | ISSN | Citations |
8161 | 0302-9743 | 4 |
PageRank | References | Authors |
0.43 | 26 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Parosh Aziz Abdulla | 1 | 2010 | 122.22 |
Mohamed Faouzi Atig | 2 | 505 | 40.94 |
Giorgio Delzanno | 3 | 845 | 61.80 |
Andreas Podelski | 4 | 2760 | 197.87 |