The Complexity of Languages Generated by Attribute Grammars

descriptionPublicationkeyboard_double_arrow_right Article 01 Feb 1986 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 15, pages 70-86 (issn: 0097-5397, eissn: 1095-7111,

Copyright policy )

Authors: Joost Engelfriet;

doi: 10.1137/0215005

The Complexity of Languages Generated by Attribute Grammars

- Summary
- Subjects
- Metrics

Abstract

Summary: 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

Analysis of algorithms and problem complexity, compilers, Formal languages and automata, alternation, string-valued attribute grammar, resource-bounded automata, semantic domain, context-free language

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	12
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average