On average behaviour of regular expressions in strong star normal form

DOI10.1142/S0129054119400227MaRDI QIDQ5205036zbMATH OpenFDO

Authors Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis

Publication date 10 December 2019

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

zbMATH Keywords

regular expressionsanalytic combinatoricsPuiseux seriesstar normal formasymptotic average case complexityconversions into finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the average complexity of strong star normal form
• Random Regular Expression Over Huge Alphabets
• scientific article; zbMATH DE number 7075888
• On the average complexity of partial derivative automata for semi-extended expressions
• On the state complexity of partial derivative automata for regular expressions with intersection

Cites work

• scientific article; zbMATH DE number 5999572 (Why is no real title available?)
• scientific article; zbMATH DE number 3167270 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Algebra.
• Analytic combinatorics
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Design of Sequential Machines from Their Regular Expressions
• Elements of automata theory. Translated from the French by Reuben Thomas
• Follow automata.
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• On the Average Size of Glushkov’s Automata
• On the average complexity of strong star normal form
• On the average size of Glushkov and partial derivative automata
• On the average state complexity of partial derivative automata: an analytic combinatorics approach
• Partial derivatives of regular expressions and finite automaton constructions
• Programming Techniques: Regular expression search algorithm
• Regular expressions into finite automata
• Simplifying regular expressions. A quantitative perspective
• THE ABSTRACT THEORY OF AUTOMATA

Cited in

(12)

• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Efficient enumeration of regular expressions for faster regular expression synthesis
• On the average state complexity of partial derivative transducers
• On the size of partial derivatives and the word membership problem
• scientific article; zbMATH DE number 1134629 (Why is no real title available?)
• On the average complexity of strong star normal form
• Regular Expressions on Average and in the Long Run
• On the average complexity of partial derivative transducers
• Random Regular Expression Over Huge Alphabets
• Extended regular expressions of star degree at most two
• On the uniform distribution of regular expressions
• Partial derivative automaton by compressing regular expressions

Describes a project that uses

Uses Software

• FAdo

This page was built for publication: On average behaviour of regular expressions in strong star normal form

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