2015 | OriginalPaper | Chapter
From -Regular Expressions to Büchi Automata via Partial Derivatives
Authors : Peter Thiemann, Martin Sulzmann
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We extend Brzozowski derivatives and partial derivatives from regular expressions to
$$\omega $$
-regular expressions and establish their basic properties. We observe that the existing derivative-based automaton constructions do not scale to
$$\omega $$
-regular expressions. We define a new variant of the partial derivative that operates on linear factors and prove that this variant gives rise to a translation from
$$\omega $$
-regular expressions to nondeterministic Büchi automata.