We present an algorithm for the recognition of rational trace languages that has a time complexity at most proportional to the number of prefixes of the input trace. In the worst case it requires O(n~α)time and O(n~α-1) space, where α is the size of the maximum clique in the independence alphabet; in the average case, it works in O (n~k) time, where k is the number of connected components of the dependence alphabet. This algorithm is based on a dynamic programming technique that can also be applied for the recognition of context-free trace languages.
展开▼
