Descriptional complexity of deterministic regular expressions

DOI10.1007/978-3-642-32589-2_56MaRDI QIDQ2912763zbMATH OpenOpenAlexFDO

Authors Katja Losemann, Wim Martens, Matthias Niewerth

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32589-2_56

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Closure properties and descriptional complexity of deterministic regular expressions
• Descriptional complexity of regular languages
• Deciding definability by deterministic regular expressions
• The complexity of regular(-like) expressions
• The complexity of regular(-like) expressions

Cited in

(16)

• Descriptional complexity of regular languages
• Analysis of an efficient reduction algorithm for random regular expressions based on universality detection
• Language operations with regular expressions of polynomial size
• Complexity of regex crosswords
• Deciding definability by deterministic regular expressions
• Closure properties and descriptional complexity of deterministic regular expressions
• The complexity of regular(-like) expressions
• Definability by weakly deterministic regular expressions with counters is decidable
• Extended Regular Expressions: Succinctness and Decidability
• scientific article; zbMATH DE number 2044501 (Why is no real title available?)
• scientific article; zbMATH DE number 871236 (Why is no real title available?)
• Deciding definability by deterministic regular expressions
• Deciding determinism of regular languages
• Quantitative Verification of Stochastic Regular Expressions
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Deciding determinism of unary languages

This page was built for publication: Descriptional complexity of deterministic regular expressions

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