The intrinsically exponential complexity of the circularity problem for attribute grammars

DOI10.1145/361227.361231MaRDI QIDQ4080746zbMATH OpenOpenAlexWikidataFDO

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

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

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

Cited in

(19)

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

This page was built for publication: The intrinsically exponential complexity of the circularity problem for attribute grammars

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