The Complexity of Languages Generated by Attribute Grammars

DOI10.1137/0215005MaRDI QIDQ3718173zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215005

zbMATH Keywords

alternationcompilerscontext-free languageresource-bounded automatasemantic domainstring-valued attribute grammar

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• On attribute grammars without attribute synthesis
• scientific article; zbMATH DE number 4080942
• scientific article; zbMATH DE number 4037255
• Relating attribute grammars and lexical-functional grammars
• scientific article; zbMATH DE number 177442

Cited in

(14)

• Pattern selector grammars and several parsing algorithms in the context- free style
• Composition and evaluation of attribute coupled grammars
• Complexity characterizations of attribute grammar languages
• Properties that characterize LOGCFL
• Relating attribute grammars and lexical-functional grammars
• Context-free hypergraph grammars have the same term-generating power as attribute grammars
• Attribute grammars and automatic complexity analysis
• Independent parallelism in finite copying parallel rewriting systems
• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• Storage products and linear control of derivations
• scientific article; zbMATH DE number 4080942 (Why is no real title available?)
• On the complexity of regular-grammars with integer attributes
• On attribute grammars without attribute synthesis
• Computational and attribute models of formal languages

This page was built for publication: The Complexity of Languages Generated by Attribute Grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3718173)