The intrinsically exponential complexity of the circularity problem for attribute grammars

DOI10.1145/361227.361231zbMath0318.68051OpenAlexW1988097631WikidataQ128297242 ScholiaQ128297242MaRDI QIDQ4080746

Mehdi Jazayeri, William C. Rounds, William F. Ogden

Publication date: 1975

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01)

Related Items

Attribute and unification grammar: A review and analysis of formalisms, Composition and evaluation of attribute coupled grammars, Complexity characterizations of attribute grammar languages, A class of algorithms which require nonlinear time to maintain disjoint sets, A near-optimal method for reasoning about action, The formal power of one-visit attribute grammars, Computational and attribute models of formal languages, Testing attribute grammars for circularity, Attribute grammars and recursive program schemes. I. II, Attribute grammars for unranked trees as a query language for structured documents, Simple multi-visit attribute grammars, The method of attributes for data flow analysis. I: Exhaustive analysis, A Survey on Decidable Equivalence Problems for Tree Transducers, Ordered attributed grammars, An order-algebraic definition of knuthian semantics, The time complexity of typechecking tree-walking tree transducers, k-visit attribute grammars, A formal methodology using attributed grammars for multiprocessing-system software development. II. Validation