I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - An Automata Approach to Some Problems on Context-free Grammars

Reference:

J. Esparza and P. Rossmanith. An automata approach to some problems on context-free grammars. In R. Valk C. Freksa, M. Jantzen, editor, Foundations of Computer Science, Potential - Theory - Cognition, number 1337 in Lecture Notes in Computer Science, pages 143–152, 1997.

Abstract:

In Chapter 4 of their book String Rewriting Systems, Book and Otto solve a number of word problems for monadic string-rewriting systems using an elegant automata-based technique. In this note we observe that the technique is also very interesting from a pedagogical point of view, since it provides a uniform solution to several elementary problems on context-free languages.

Suggested BibTeX entry:

@inproceedings{ER97,
    author = {J. Esparza and P. Rossmanith},
    booktitle = {Foundations of Computer Science, Potential - Theory - Cognition},
    editor = {C. Freksa, M. Jantzen, R. Valk},
    number = {1337},
    pages = {143--152},
    series = {{Lecture Notes in Computer Science}},
    title = {An Automata Approach to Some Problems on Context-free Grammars},
    year = {1997}
}

GZipped PostScript (49 kB)
PDF (174 kB)