×

Complexity results for prefix grammars. (English) Zbl 1133.68357

Summary: Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars

MSC:

68Q42 Grammars and rewriting systems
03D03 Thue and Post systems, etc.
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI Numdam Numdam EuDML

References:

[1] J.R. Büchi , Regular canonical systems . Archiv Math. Logik und Grundlagenforschung 6 ( 1964 ) 91 - 111 . Article | Zbl 0129.26102 · Zbl 0129.26102
[2] J.R. Büchi , Finite Automata, their Algebras and Grammars . Springer, Berlin-Heidelberg-New York ( 1989 ). MR 1016145 | Zbl 0715.68062 · Zbl 0715.68062
[3] J.R. Büchi and W.H. Hosken , Canonical systems which produce periodic sets . Math. Syst. Theor. 4 ( 1970 ) 81 - 90 . Zbl 0188.33104 · Zbl 0188.33104
[4] D. Caucal , On the regular structure of prefix rewriting . Theor. Comput. Sci. 106 ( 1992 ) 61 - 86 . Zbl 0780.68077 · Zbl 0780.68077
[5] A.K. Chandra , D.C. Kozen and L.J. Stockmeyer , Alternation . J. Association Computing Machinery 28 (2981) 114 - 133 . Zbl 0473.68043 · Zbl 0473.68043
[6] J. Esparza , D. Hansel , P. Rossmanith and S. Schwoon , Efficient algorithms for model checking pushdown systems , in Proc. of 12th International Conference on Computer Aided Verification (CAV), edited by E.A. Emerson and A.P. Sistla (Springer). Lect. Notes Comput. Sci. 1855 ( 2000 ) 232 - 247 . Zbl 0974.68116 · Zbl 0974.68116
[7] J. Esparza , A. Kucera and S. Schwoon , Model checking LTL with regular valuations for pushdown systems . Inform. Comput. 186 ( 2003 ) 355 - 376 . Zbl 1078.68081 · Zbl 1078.68081
[8] M. Frazier and C.D. Page Jr , Prefix grammars: An alternative characterization of the regular languages . Inform. Process. Lett. 51 ( 1994 ) 67 - 71 . Zbl 0813.68125 · Zbl 0813.68125
[9] S.A. Greibach , A note on pushdown store automata and regular systems , in Proc. of the AMS 18 ( 1967 ) 263 - 268 . Zbl 0183.01703 · Zbl 0183.01703
[10] J.E. Hopcroft and R.M. Karp , A linear algorithm for testing the equivalence of finite automata . Report TR 71 - 114 , Department of Computer Science, Cornell University ( 1971 ).
[11] N.D. Jones and W.T. Laaser , Complete problems for deterministic polynomial time . Theor. Comput. Sci. 3 ( 1977 ) 105 - 117 . Zbl 0352.68068 · Zbl 0352.68068
[12] M. Kratko , Formal post calculi and finite automata . Problemy Kibernet. 17 ( 1966 ) 41 - 65 . In Russian. Zbl 0217.01003 · Zbl 0217.01003
[13] R.E. Ladner , R.J. Lipton and L.J. Stockmeyer , Alternating pushdown and stack automata . SIAM J. Comput. 13 ( 1984 ) 135 - 155 . Zbl 0538.68039 · Zbl 0538.68039
[14] A.R. Meyer and L.J. Stockmeyer , The equivalence problem for regular expressions with squaring requires exponential space , in Proc. of the 13th Annual IEEE Symposium on Switching and Automata Theory, College Park (Maryland) ( 1972 ) 125 - 129 .
[15] C.H. Papadimitriou , Computational Complexity . Addison Wesley ( 1994 ). MR 1251285 | Zbl 0833.68049 · Zbl 0833.68049
[16] H. Petersen , Prefix rewriting and descriptional complexity . J. Autom. Lang. Comb. 5 ( 2000 ) 245 - 254 . Zbl 0971.68083 · Zbl 0971.68083
[17] B. Ravikumar and L. Quan , Efficient algorithms for prefix grammars . Available at http://www.cs.sonoma.edu/ ravi (2002).
[18] L.J. Stockmeyer and A.R. Meyer , Word problems requiring exponential time , in Proc. of the 5th ACM Symposium on Theory of Computing (STOC’73), Austin (Texas) ( 1973 ) 1 - 9 . Zbl 0359.68050 · Zbl 0359.68050
[19] H. Straubing , Finite Automata , Formal Logic, and Circuit Complexity. Birkhäuser ( 1994 ). MR 1269544 | Zbl 0816.68086 · Zbl 0816.68086
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.