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)

Full work available at URL https://doi.org/10.1142/S0129054119400227

zbMATH Keywords

analytic combinatoricsasymptotic average case complexityconversions into finite automataPuiseux seriesregular expressionsstar normal form

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

• 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.
• 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?)
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• On the average complexity of strong star normal form
• On the average size of Glushkov and partial derivative automata
• On the Average Size of Glushkov’s 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

(14)

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

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)