Complexity results for prefix grammars

Markus Lohrey; Holger Petersen

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

  • Volume: 39, Issue: 2, page 391-401
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Lohrey, Markus, and Petersen, Holger. "Complexity results for prefix grammars." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.2 (2005): 391-401. <http://eudml.org/doc/245436>.

@article{Lohrey2005,
abstract = {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.},
author = {Lohrey, Markus, Petersen, Holger},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {rewriting systems; regular languages; computational complexity},
language = {eng},
number = {2},
pages = {391-401},
publisher = {EDP-Sciences},
title = {Complexity results for prefix grammars},
url = {http://eudml.org/doc/245436},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Lohrey, Markus
AU - Petersen, Holger
TI - Complexity results for prefix grammars
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 2
SP - 391
EP - 401
AB - 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.
LA - eng
KW - rewriting systems; regular languages; computational complexity
UR - http://eudml.org/doc/245436
ER -

References

top
  1. [1] J.R. Büchi, Regular canonical systems. Archiv Math. Logik und Grundlagenforschung 6 (1964) 91–111. Zbl0129.26102
  2. [2] J.R. Büchi, Finite Automata, their Algebras and Grammars. Springer, Berlin-Heidelberg-New York (1989). Zbl0715.68062MR1016145
  3. [3] J.R. Büchi and W.H. Hosken, Canonical systems which produce periodic sets. Math. Syst. Theor. 4 (1970) 81–90. Zbl0188.33104
  4. [4] D. Caucal, On the regular structure of prefix rewriting. Theor. Comput. Sci. 106 (1992) 61–86. Zbl0780.68077
  5. [5] A.K. Chandra, D.C. Kozen and L.J. Stockmeyer, Alternation. J. Association Computing Machinery 28 (2981) 114–133. Zbl0473.68043
  6. [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. Zbl0974.68116
  7. [7] J. Esparza, A. Kucera and S. Schwoon, Model checking LTL with regular valuations for pushdown systems. Inform. Comput. 186 (2003) 355–376. Zbl1078.68081
  8. [8] M. Frazier and C.D. Page Jr, Prefix grammars: An alternative characterization of the regular languages. Inform. Process. Lett. 51 (1994) 67–71. Zbl0813.68125
  9. [9] S.A. Greibach, A note on pushdown store automata and regular systems, in Proc. of the AMS 18 (1967) 263–268. Zbl0183.01703
  10. [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. [11] N.D. Jones and W.T. Laaser, Complete problems for deterministic polynomial time. Theor. Comput. Sci. 3 (1977) 105–117. Zbl0352.68068
  12. [12] M. Kratko, Formal post calculi and finite automata. Problemy Kibernet. 17 (1966) 41–65. In Russian. Zbl0217.01003
  13. [13] R.E. Ladner, R.J. Lipton and L.J. Stockmeyer, Alternating pushdown and stack automata. SIAM J. Comput. 13 (1984) 135–155. Zbl0538.68039
  14. [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. [15] C.H. Papadimitriou, Computational Complexity. Addison Wesley (1994). Zbl0833.68049MR1251285
  16. [16] H. Petersen, Prefix rewriting and descriptional complexity. J. Autom. Lang. Comb. 5 (2000) 245–254. Zbl0971.68083
  17. [17] B. Ravikumar and L. Quan, Efficient algorithms for prefix grammars. Available at http://www.cs.sonoma.edu/~ravi (2002). 
  18. [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. Zbl0359.68050
  19. [19] H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser (1994). Zbl0816.68086MR1269544

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.