A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages

DOI10.1016/0304-3975(88)90008-4MaRDI QIDQ1837536zbMATH OpenOpenAlexFDO

Authors Stephan Heilbrunner

Publication date 1983

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(88)90008-4

zbMATH Keywords

Post's correspondence problemLL-regular languageLR-regular languagerelative decision problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20)

Cites work

• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 3562527 (Why is no real title available?)
• scientific article; zbMATH DE number 3569814 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Corrigendum: `` Lower Bounds and Reductions Between Grammar Problems
• LR-regular grammars - an extension of LR(k) grammars
• Noncanonical Extensions of Bottom-Up Parsing Techniques
• On LL-regular grammars
• On the Parsing of Deterministic Languages
• On the translation of languages from left to right
• Optimization of LR(k) parsers
• Properties of deterministic top-down grammars
• Two iteration theorems for the LL(k) languages

Cited in

(1)

• Left-to-right regular languages and two-way restarting automata

This page was built for publication: A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages

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