On the complexity of regular-grammars with integer attributes

DOI10.1016/J.JCSS.2010.05.006MaRDI QIDQ632805zbMATH OpenOpenAlexFDO

Authors M. Manna, Francesco Scarcello, N. Leone

Publication date 28 March 2011

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2010.05.006

zbMATH Keywords

computational complexitycontext-free grammarsattribute grammarsmodels of computationregular grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• On attribute grammars without attribute synthesis
• The Complexity of Languages Generated by Attribute Grammars
• Relating attribute grammars and lexical-functional grammars
• scientific article; zbMATH DE number 627410
• Attribute grammars and automatic complexity analysis

Cites work

• scientific article; zbMATH DE number 4157906 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4080911 (Why is no real title available?)
• scientific article; zbMATH DE number 3560742 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1951122 (Why is no real title available?)
• scientific article; zbMATH DE number 2080403 (Why is no real title available?)
• scientific article; zbMATH DE number 1462097 (Why is no real title available?)
• scientific article; zbMATH DE number 870438 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3238658 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• Attribute grammars for unranked trees as a query language for structured documents
• Attribute grammars, applications and systems. International summer school SAGA, Prague, Czechoslovakia, June 4-13, 1991. Proceedings
• Attribute grammars. Definitions, systems and bibliography
• Attributed translations
• Classes of languages and linear-bounded automata
• Complexity characterizations of attribute grammar languages
• Deterministic context free languages
• Division in logspace-uniform NC
• Expressiveness of structured document query languages based on attribute grammars
• Fast multiplication of large numbers
• Faster integer multiplication
• GAG: a practical compiler generator
• On Relating Time and Space to Size and Depth
• On the Tape Complexity of Deterministic Context-Free Languages
• One application of real-valued interpretation of formal power series.
• Parsing regular grammars with finite lookahead
• Relating logic programs and attribute grammars
• Semantics of context-free languages
• The Hardest Context-Free Language
• Tree-size bounded alternation
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(2)

• Magic sets for disjunctive Datalog programs
• Complexity of super-coherence problems in ASP

Describes a project that uses

Uses Software

• GAG
• CONSTRUCTOR

This page was built for publication: On the complexity of regular-grammars with integer attributes

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