On the complexity of regular-grammars with integer attributes
From MaRDI portal
Publication:632805
DOI10.1016/j.jcss.2010.05.006zbMath1218.68093OpenAlexW2037019297MaRDI QIDQ632805
Francesco Scarcello, Marco Manna, Nicola 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
computational complexitycontext-free grammarsattribute grammarsmodels of computationregular grammars
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity characterizations of attribute grammar languages
- Tree-size bounded alternation
- Parsing regular grammars with finite lookahead
- GAG: a practical compiler generator
- Attribute grammars, applications and systems. International summer school SAGA, Prague, Czechoslovakia, June 4-13, 1991. Proceedings
- Attribute grammars. Definitions, systems and bibliography
- Attributed translations
- One application of real-valued interpretation of formal power series.
- Attribute grammars for unranked trees as a query language for structured documents
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Fast multiplication of large numbers
- Division in logspace-uniformNC1
- Expressiveness of structured document query languages based on attribute grammars
- Faster Integer Multiplication
- Relating logic programs and attribute grammars
- On Relating Time and Space to Size and Depth
- On the Tape Complexity of Deterministic Context-Free Languages
- The Hardest Context-Free Language
- Deterministic context free languages
- Semantics of context-free languages
- Classes of languages and linear-bounded automata
