Complexity characterizations of attribute grammar languages

DOI10.1016/0890-5401(88)90025-9zbMath0672.68035OpenAlexW1971958814MaRDI QIDQ1120290

Christos H. Papadimitriou, Sophocles Efremidis, Martha Sideris

Publication date: 1988

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(88)90025-9

zbMATH Keywords

context free languagesattribute grammarscontext free grammarsexpressive power of attribute grammarslanguage generators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (2)

On the complexity of regular-grammars with integer attributes ⋮ On attribute grammars without attribute synthesis

Cites Work

• The Complexity of Languages Generated by Attribute Grammars
• The intrinsically exponential complexity of the circularity problem for attribute grammars
• Semantics of context-free languages

This page was built for publication: Complexity characterizations of attribute grammar languages