The Complexity of Languages Generated by Attribute Grammars
- 1 February 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (1) , 70-86
- https://doi.org/10.1137/0215005
Abstract
A string-valued attribute grammar (SAG) has a semantic domain of strings over some alphabet, with concatenation as basic operation. It is shown that the output language (i.e., the range of the translation) of a SAG is log-space reducible to a context-free language.Keywords
This publication has 26 references indexed in Scilit:
- Three hierarchies of transducersTheory of Computing Systems, 1981
- A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute GrammarsJournal of the ACM, 1981
- Time and space complexity of inside-out macro languagesInternational Journal of Computer Mathematics, 1981
- AlternationJournal of the ACM, 1981
- On the Tape Complexity of Deterministic Context-Free LanguagesJournal of the ACM, 1978
- The intrinsically exponential complexity of the circularity problem for attribute grammarsCommunications of the ACM, 1975
- Bottom-up and top-down tree transformations— a comparisonTheory of Computing Systems, 1975
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Mappings and grammars on treesTheory of Computing Systems, 1970
- Semantics of context-free languagesTheory of Computing Systems, 1968