An efficient automata approach to some problems on context-free grammars

[en] Book and Otto (1993) 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.

Disciplines :

Computer science

Author, co-author :

Bouajjani, Ahmed

Esparza, Javier

Finkel, Alain

Maler, Oded

Rossmanith, Peter

Willems, Bernard

Wolper, Pierre ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique (parallélisme et banques de données)

Language :

English

Title :

An efficient automata approach to some problems on context-free grammars

Publication date :

June 2000

Journal title :

Information Processing Letters

ISSN :

0020-0190

Publisher :

Elsevier Science

Volume :

Issue :

5-6

Pages :

221-227

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 02 December 2009

Statistics

Number of views

82 (1 by ULiège)

Number of downloads

112 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1976.
R.F. Book, F. Otto, String-Rewriting Systems, Texts and Monographs in Computer Science, Springer, Berlin, 1993.
A. Bouajjani, O. Maler, Reachability analysis of pushdown automata, in: Proc. INFINITY'96 Workshop, Technical Report MIP-9614, Faculty of Mathematics and Computer Science, University of Passau, 1996.
A. Bouajjani, J. Esparza, O. Maler, Reachability analysis of pushdown automata: Application to model-checking, in: A. Mazurkiewicz, J. Winkowski (Eds.), Proc. CONCUR'97, Lecture Notes in Comput. Sci., Vol. 1243, Springer, Berlin, 1997, pp. 135-150.
J.R. Büchi, Regular canonical systems and finite automata, Arch. Math. Logik Grundl. 6 (1964) 91-111.
J.R. Büchi, Finite Automata, Their Algebras and Grammars, Springer, Berlin, 1988.
D. Caucal, On the regular structure of prefix rewriting, Theoret. Comput. Sci. 106 (1) (1992) 61-86.
W.F. Dowling, J.H. Gallier, Linear-time algorithms for testing the satisfiability of prepositional Horn formulae, J. Logic Programming 3 (1984) 267-284.
J. Esparza, P. Rossmanith, An automata approach to some problems on context-free grammars, in: C. Freksa, M. Jantzen, R. Valk (Eds.), Foundations of Computer Science: Potential, Theory, Cognition, Lecture Notes in Comput. Sci., Vol. 1337, 1997, pp. 143-152.
A. Finkel, B. Willems, P. Wolper, A direct symbolic approach to model-checking pushdown systems, in: Proc. INFINITY'97 Workshop, Electronic Notes in Theoretical Computer Science, Vol. 9, 1997.
J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979.
D.H. Younger, Recognition and parsing of context-free languages in time n3, Inform, and Control 10 (1967) 189-208.