|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/54
|
| Title: | Structural equivalence and ETOL grammars |
| Authors: | Salomaa, Kai
Wood, Derick
Yu, Sheng |
| Issue Date: | Sep-1995 |
| Series/Report no.: | Computer Science Technical Report ; HKUST-CS95-44 |
| Abstract: | For a given context-sensitive grammar G we construct ET0L grammars G_1 and G_2 that are structurally equivalent if and only if the language generated by G is empty, which implies that structural equivalence is undecidable for ET0L grammars. In contrast, structural equivalence is decidable for E0L grammars and for extended E0L grammars. In fact, we show that structural equivalence is undecidable for propagating ET0L grammars in which the number of tables is restricted to be at most two. A stronger notion of equivalence that requires the sets of syntax trees to be isomorphic is shown to be decidable for ET0L grammars. |
| URI: | http://hdl.handle.net/1783.1/54 |
| Appears in Collections: | CSE Technical Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| tr9544.pdf | | 281Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
