On the degrees of non-regularity and non-context-freeness

DOI10.1016/j.jcss.2019.09.003zbMath1447.68006OpenAlexW2981361234WikidataQ126979734 ScholiaQ126979734MaRDI QIDQ2009649

Victor Mitrana, Henning Bordihn

Publication date: 29 November 2019

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.2019.09.003

zbMATH Keywords

context-free grammarcontext-sensitive grammardegree of non-context-freenessdegree of non-regularity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Jump complexity of finite automata with translucent letters ⋮ On the Degree of Extension of Some Models Defining Non-Regular Languages ⋮ On the group memory complexity of extended finite automata over groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pushdown automata and constant height: decidability and bounds
• Time-bounded grammars and their languages
• Substitution and bounded languages
• Measuring nondeterminism in pushdown automata
• A note on phrase structure grammars
• The Rational Index: A Complexity Measure for Languages
• Non-context-free grammars generating context-free languages
• A note on asymmetry in phrase structure grammars
• Deterministic context free languages
• Mappings which preserve context sensitive languages
• Two-way languages
• A regularity test for pushdown machines
• An analog of a theorem about context-free languages
• Terminal Context in Context-Sensitive Grammars
• Discontinuity and asymmetry in phrase structure grammars