On the state complexity of partial derivative automata for regular expressions with intersection

DOI10.1007/978-3-319-41114-9_4MaRDI QIDQ2829969zbMATH OpenOpenAlexFDO

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

Publication date 9 November 2016

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01633952/file/416473_1_En_4_Chapter.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the average complexity of partial derivative automata for semi-extended expressions
• On the average state complexity of partial derivative automata: an analytic combinatorics approach
• Partial derivatives of an extended regular expression
• On the Average Number of States of Partial Derivative Automata
• Partial Derivative Automaton for Regular Expressions with Shuffle

Cites work

• scientific article; zbMATH DE number 2086412 (Why is no real title available?)
• A general framework for the derivation of regular expressions
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• A note on the space complexity of some decision problems for finite automata
• Analytic combinatorics
• Derivatives of Regular Expressions
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• From Mirkin's prebases to Antimirov's word partial derivatives
• On the average size of Glushkov and partial derivative automata
• On the average state complexity of partial derivative automata: an analytic combinatorics approach
• Partial Derivative Automaton for Regular Expressions with Shuffle
• Partial derivatives of an extended regular expression
• Partial derivatives of regular expressions and finite automaton constructions
• Rewriting extended regular expressions
• Succinctness of regular expressions with interleaving, intersection and counting
• Succinctness of the complement and intersection of regular expressions

Cited in

(9)

• On the Average Number of States of Partial Derivative Automata
• On the average state complexity of partial derivative transducers
• Partial Derivative Automaton for Regular Expressions with Shuffle
• Position automaton construction for regular expressions with intersection
• On average behaviour of regular expressions in strong star normal form
• On the average complexity of partial derivative automata for semi-extended expressions
• On the average complexity of partial derivative transducers
• Partial derivatives of an extended regular expression
• On the average state complexity of partial derivative automata: an analytic combinatorics approach

Describes a project that uses

Uses Software

• PERL

This page was built for publication: On the state complexity of partial derivative automata for regular expressions with intersection

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