Non-self-embedding grammars and descriptional complexity

DOI10.3233/FI-2021-2036MaRDI QIDQ5164870zbMATH OpenOpenAlexFDO

Authors Giovanni Pighizzini, Luca Prigioniero

Publication date 15 November 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2021-2036

zbMATH Keywords

context-free grammarsdescriptional complexitybounded languages

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Non-self-embedding grammars, constant-height pushdown automata, and limited automata
• Non-self-embedding grammars, constant-height pushdown automata, and limited automata
• scientific article; zbMATH DE number 1962766
• Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata
• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

Cites work

• scientific article; zbMATH DE number 3173216 (Why is no real title available?)
• scientific article; zbMATH DE number 5344975 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1962766 (Why is no real title available?)
• A new algorithm for regularizing one-letter context-free grammars.
• Complexity of normal form grammars
• Descriptional complexity of bounded regular languages
• Finite automata and unary languages
• Investigations on automata and languages over a unary alphabet
• Magic numbers in the state hierarchy of finite automata
• On certain formal properties of grammars
• Two Families of Languages Related to ALGOL
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.

Cited in

(5)

• Non-self-embedding grammars, constant-height pushdown automata, and limited automata
• Non-self-embedding grammars, constant-height pushdown automata, and limited automata
• scientific article; zbMATH DE number 3309208 (Why is no real title available?)
• scientific article; zbMATH DE number 1962766 (Why is no real title available?)
• scientific article; zbMATH DE number 4203730 (Why is no real title available?)

This page was built for publication: Non-self-embedding grammars and descriptional complexity

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