Regular Closure of Deterministic Languages

DOI10.1137/S009753979528682XMaRDI QIDQ4268872zbMATH OpenFDO

Authors E. Bertsch, Mark-Jan Nederhof

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S009753979528682X

zbMATH Keywords

context-free languagesregular languages

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 480523
• scientific article; zbMATH DE number 3868645
• Closure properties and descriptional complexity of deterministic regular expressions
• scientific article; zbMATH DE number 6606340
• Finite turns and the regular closure of linear context-free languages

Cited in

(22)

• A closure property of regular languages
• Closure of finite-state automaton languages
• Detecting useless transitions in pushdown automata
• A pumping lemma for regular closure of prefix-free languages
• Boolean kernels of context-free languages
• Recognizing pro-\(\mathrm{R}\) closures of regular languages
• Finite turns and the regular closure of linear context-free languages
• Kleene Closure on Regular and Prefix-Free Languages
• Kernels of sub-classes of context-free languages
• Regulated Nondeterminism in Pushdown Automata
• On Extended Regular Expressions
• scientific article; zbMATH DE number 3919849 (Why is no real title available?)
• Detecting useless transitions in pushdown automata
• scientific article; zbMATH DE number 6542558 (Why is no real title available?)
• Left quotients of deterministic context-free languages
• Kernels of context-free languages
• Computational model for parsing expression grammars
• A linear-time simulation of deterministic \(d\)-limited automata
• Fast parallel recognition of LR language suffixes
• Regulated nondeterminism in pushdown automata
• Context-dependent nondeterminism for pushdown automata
• Closure properties and complexity of rational sets of regular languages

This page was built for publication: Regular Closure of Deterministic Languages

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