Name
Abstract | ||
|---|---|---|
In this paper, we investigate the complexity of deciding trace, maximal trace and omega-trace equivalences for finite state processes and recursively defined processes specified by normed context-free grammars (CFGs) in Greibach normal form (GNF). The main results are as follows: (1) Trace, maximal trace and omega-trace equivalences for processes specified by normed GNF CFGs are all undecidable. For this class of processes, the regularity problem with respect to trace, maximal trace or omega-trace equivalence is also undecidable. Moreover, all these undecidability results hold even for locally unary processes. For processes specified by unary GNF CFGs, the maximal trace equivalence is PI2p-complete while the omega-trace equivalence is NL-complete and the trace equivalence is decidable in polynomial time by a dynamic programming algorithm. (2) Trace, maximal trace and omega-trace equivalences for finite state processes are PSPACE-complete. This holds even for locally unary finite state processes. For unary finite state processes, the maximal trace equivalence is co-NP-complete while trace and omega-trace equivalences are NL-complete. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1016/0020-0255(93)90031-G | Inf. Sci. |
Keywords | Field | DocType |
trace equivalence | Discrete mathematics,Dynamic programming,Unary operation,Decidability,Equivalence (measure theory),Greibach normal form,Time complexity,Mathematics,Recursion,Undecidable problem | Journal |
Volume | Issue | ISSN |
72 | 1-2 | 0020-0255 |
Citations | PageRank | References |
2 | 0.43 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dung T. Huynh | 1 | 434 | 39.60 |
| Lu Tian | 2 | 13 | 2.57 |