Automata for regular expressions with shuffle

DOI10.1016/j.ic.2017.08.013zbMath1390.68378OpenAlexW2752548843MaRDI QIDQ1706150

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

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

regular expressionsfinite automatapartial derivativesanalytic combinatoricsaverage caseposition automatashuffle operation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (10)

Manipulation of regular expressions using derivatives: an overview ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Location automata for regular expressions with shuffle and intersection ⋮ Average complexity of partial derivatives for synchronised shuffle expressions ⋮ Location automata for synchronised shuffle expressions ⋮ On the average complexity of partial derivative transducers ⋮ On the Average State Complexity of Partial Derivative Transducers ⋮ Location based automata for expressions with shuffle ⋮ Unnamed Item ⋮ The commutative closure of shuffle languages over group languages is regular

Uses Software

• FAdo

Cites Work

• From regular expressions to deterministic automata
• Partial derivatives of regular expressions and finite automaton constructions
• Succinctness of regular expressions with interleaving, intersection and counting
• Canonical derivatives, partial derivatives and finite automaton constructions.
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Derivatives for Regular Shuffle Expressions
• Derivatives of Regular Expressions and an Application
• ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• On the Average Size of Glushkov’s Automata
• ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA
• Unnamed Item

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