A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars

DOI10.1145/322276.322283zbMath0468.68056OpenAlexW2003451210MaRDI QIDQ3922174

Mehdi Jazayeri

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322276.322283

zbMATH Keywords

exponential timealternating Turing machines

Mathematics Subject Classification ID

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

Related Items (1)

The time complexity of typechecking tree-walking tree transducers

This page was built for publication: A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars