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

Authors
Bouajjani, A Esparza, J Finkel, A Maler, O Rossmanith, P Willems, B Wolper, P
Citation
A. Bouajjani et al., An efficient automats approach to some problems on context-free grammars, INF PROCESS, 74(5-6), 2000, pp. 221-227
Citations number
12
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
74
Issue
5-6
Year of publication
2000
Pages
221 - 227
Database
ISI
SICI code
0020-0190(20000630)74:5-6<221:AEAATS>2.0.ZU;2-O
Abstract
Book and Otto (1993) solve a number of word problems for monadic string-rew riting systems using an elegant automata-based technique. In this note we o bserve that the technique is also very interesting from a pedagogical point of view, since it provides a uniform solution to several elementary proble ms on context-free languages. (C) 2000 Elsevier Science B.V, All rights res erved.