|
 ABSTRACT
The equivalence problem for Kleene's regular expressions has several effective solutions, all of which are computationally inefficient. In [1], we showed that this inefficiency is an inherent property of the problem by showing that the problem of membership in any arbitrary context-sensitive language was easily reducible to the equivalence problem for regular expressions. We also showed that with a squaring abbreviation ( writing (E)2 for E×E) the equivalence problem for expressions required computing space exponential in the size of the expressions. In this paper we consider a number of similar decidable word problems from automata theory and logic whose inherent computational complexity can be precisely characterized in terms of time or space requirements on deterministic or nondeterministic Turing machines. The definitions of the word problems and a table summarizing their complexity appears in the next section. More detailed comments and an outline of some of the proofs follows in the remaining sections. Complete proofs will appear in the forthcoming papers [9, 10, 13]. In the final section we describe some open problems.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Meyer, A.R. and L.J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space, 13th Annual IEEE Symp. on Switching and Automata Theory, Oct., 1972, 125-129.
|
| |
2
|
|
 |
3
|
|
| |
4
|
Karp, R. Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, ed., Plenum Press, N.Y., 85-104.
|
| |
5
|
Seiferas, J. Translations in the Nondeterministic Tape and Time Hierarchies, in preparation.
|
| |
6
|
|
| |
7
|
|
| |
8
|
|
| |
9
|
Meyer, A. and Stockmeyer, L. Some Inherently Difficult Word Problems, Part I, to appear in Journal of Computer and System Sciences.
|
| |
10
|
Meyer, A. and Stockmeyer, L. Nonelementary Word Problems in Automata and Logic, to be presented at the Amer. Math. Soc. Symp. on the Complexity of Computation, New York, April 1973.
|
| |
11
|
Bauer, M., D. Brand, M. Fischer, A. Meyer, and M. Paterson. A Note on Disjunctive Form Tautologies, SIGACT NEWS, 1973, to appear.
|
| |
12
|
Savitch, W. Relationships Between Nondeterministic and Deterministic Tape Complexities, J. Computer and System Sciences Vol. 4, 1970, 177-192.
|
| |
13
|
Stockmeyer, L. Some Inherently Difficult Word Problems, Part II, in preparation.
|
| |
14
|
|
| |
15
|
Wiener, P. and T. Kameda. On the Reduction of Non-Deterministic Automata, Tech. Report No. 57, Dept. of Electrical Engineering, Princeton University, 1968.
|
| |
16
|
|
| |
17
|
|
CITED BY 100
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Daniela Florescu , Alon Levy , Dan Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 01-04, 1998, Seattle, Washington, United States
|
|
|
|
|
|
John R. Gilbert , Thomas Lengauer , Robert Endre Tarjan, The pebbling problem is complete in polynomial space, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.237-248, April 30-May 02, 1979, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
Alberto Bertoni , Giancarlo Mauri , Nicoletta Sabadini, A characterization of the class of functions computable in polynomial time on Random Access Machines, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.168-176, May 11-13, 1981, Milwaukee, Wisconsin, United States
|
|
|
|
|
|
|
|
|
|
|
|
I. H. Sudborough, On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, Proceedings of the eighth annual ACM symposium on Theory of computing, p.141-148, May 03-05, 1976, Hershey, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paris C. Kanellakis , Scott A. Smolka, CCS expressions, finite state processes, and three problems of equivalence, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.228-240, August 17-19, 1983, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
E. Cardoza , R. Lipton , A. R. Meyer, Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report), Proceedings of the eighth annual ACM symposium on Theory of computing, p.50-54, May 03-05, 1976, Hershey, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H. B. Hunt, III , D. J. Rosenkrantz, Computational parallels between the regular and context-free languages, Proceedings of the sixth annual ACM symposium on Theory of computing, p.64-74, April 30-May 02, 1974, Seattle, Washington, United States
|
|
|
Richard Ladner , Nancy Lynch , Alan Selman, Comparison of polynomial-time reducibilities, Proceedings of the sixth annual ACM symposium on Theory of computing, p.110-121, April 30-May 02, 1974, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
Nancy Lynch , Albert Meyer , Michael Fischer, Sets that don't help, Proceedings of the fifth annual ACM symposium on Theory of computing, p.130-134, April 30-May 02, 1973, Austin, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sanjeev Arora , Yuval Rabani , Umesh Vazirani, Simulating quadratic dynamical systems is PSPACE-complete (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.459-467, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Faron Moller , Scott A. Smolka, On the computational complexity of bisimulation, redux, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.55-59, June 08-08, 2003, San Diego, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.4