On complexity of grammars related to the safety problem

DOI10.1016/J.TCS.2007.07.043MaRDI QIDQ2465626zbMATH OpenOpenAlexFDO

Authors Tomasz Jurdziński

Publication date 7 January 2008

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

Full work available at URL https://doi.org/10.1016/j.tcs.2007.07.043

zbMATH Keywords

automata and formal languagesaccessibility problemleftist grammarsprotection system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)

Recommendations

• On Complexity of Grammars Related to the Safety Problem
• Leftist grammars and the Chomsky hierarchy
• Leftist Grammars Are Non-primitive Recursive
• Fundamentals of Computation Theory
• Safety in grammatical protection systems

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• A Linear Time Algorithm for Deciding Subject Security
• CONCUR 2005 – Concurrency Theory
• Fundamentals of Computation Theory
• Leftist grammars and the Chomsky hierarchy
• On the decidability of accessibility problems (extended abstract)
• Protection in operating systems
• Safety in grammatical protection systems

Cited in

(8)

• Automata, Languages and Programming
• Toward a compositional theory of leftist grammars and transformations
• Safety in grammatical protection systems
• Leftist grammars and the Chomsky hierarchy
• Fundamentals of Computation Theory
• On Complexity of Grammars Related to the Safety Problem
• On the decidability of accessibility problems (extended abstract)
• Leftist Grammars Are Non-primitive Recursive

This page was built for publication: On complexity of grammars related to the safety problem

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