Reordering Derivatives of Trace Closures of Regular Languages (Full Version)

Introduction

Preliminaries on Word Languages

Regular Languages

Derivatives of a Language

Brzozowski Derivative

Antimirov Derivative

Trace Closures of Regular Languages

Trace Closure of a Word Language

Trace-Closing Semantics of Regular Expressions

Properties of Trace Closures of Regular Languages

Rational and Recognizable Languages of Monoids

Reordering Derivatives

Reordering Derivative of a Language

Brzozowski Reordering Derivative

Antimirov Reordering Derivative

Star-Connected Expressions

Automaton Finiteness for Star-Connected Expressions

Uniform Scattering Rank of a Language

Scattering Rank vs. Uniform Scattering Rank

Star-Connected Languages Have Uniform Rank

Antimirov Reordering Derivative and Uniform Rank

Refined Antimirov Reordering Derivative

Automaton Finiteness for Regular Expressions with Uniform Rank