Non-self-embedding grammars and descriptional complexity
From MaRDI portal
Publication:5164870
DOI10.3233/FI-2021-2036OpenAlexW3160260578MaRDI QIDQ5164870FDOQ5164870
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
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
- Title not available (Why is that?)
- On certain formal properties of grammars
- Title not available (Why is that?)
- Finite automata and unary languages
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Two Families of Languages Related to ALGOL
- Complexity of normal form grammars
- Magic numbers in the state hierarchy of finite automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new algorithm for regularizing one-letter context-free grammars.
- Descriptional complexity of bounded regular languages
- Investigations on automata and languages over a unary alphabet
Cited In (5)
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)