# Complexity results for prefix grammars

Markus Lohrey; Holger Petersen

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topLohrey, Markus, and Petersen, Holger. "Complexity results for prefix grammars." RAIRO - Theoretical Informatics and Applications 39.2 (2010): 391-401. <http://eudml.org/doc/92772>.

@article{Lohrey2010,

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},

keywords = {Rewriting systems; regular languages; computational complexity; rewriting systems},

language = {eng},

month = {3},

number = {2},

pages = {391-401},

publisher = {EDP Sciences},

title = {Complexity results for prefix grammars},

url = {http://eudml.org/doc/92772},

volume = {39},

year = {2010},

}

TY - JOUR

AU - Lohrey, Markus

AU - Petersen, Holger

TI - Complexity results for prefix grammars

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

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; rewriting systems

UR - http://eudml.org/doc/92772

ER -

## References

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

## NotesEmbed ?

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