Automata for regular expressions with shuffle

DOI10.1016/J.IC.2017.08.013MaRDI QIDQ1706150zbMATH OpenOpenAlexFDO

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

Publication date 21 March 2018

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2017.08.013

zbMATH Keywords

partial derivativesfinite automataaverage caseregular expressionsanalytic combinatoricsposition automatashuffle operation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Partial Derivative Automaton for Regular Expressions with Shuffle
• On the Average Number of States of Partial Derivative Automata
• On the average state complexity of partial derivative automata: an analytic combinatorics approach
• On the average size of Glushkov and partial derivative automata
• On the State Complexity of the Shuffle of Regular Languages

Cites work

• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Derivatives for regular shuffle expressions
• Derivatives of regular expressions and an application
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• From Mirkin's prebases to Antimirov's word partial derivatives
• From regular expressions to deterministic automata
• On the Average Size of Glushkov’s Automata
• 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
• Succinctness of regular expressions with interleaving, intersection and counting

Cited in

(15)

• On the shuffle automaton size for words
• Location automata for regular expressions with shuffle and intersection
• On the average state complexity of partial derivative transducers
• Partial Derivative Automaton for Regular Expressions with Shuffle
• The prefix automaton
• Average complexity of partial derivatives for synchronised shuffle expressions
• Manipulation of regular expressions using derivatives: an overview
• Location based automata for expressions with shuffle
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
• Derivatives and partial derivatives for regular shuffle expressions
• Location automata for synchronised shuffle expressions
• Structural properties of shuffle automata
• On the average complexity of partial derivative transducers
• Derivatives for regular shuffle expressions
• The commutative closure of shuffle languages over group languages is regular

Describes a project that uses

Uses Software

• FAdo

This page was built for publication: Automata for regular expressions with shuffle

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