Derived-Term Automata for Extended Weighted Rational Expressions

DOI10.1007/978-3-319-46750-4_20zbMATH Open1482.68125arXiv1605.01530OpenAlexW2346998017MaRDI QIDQ3179410FDOQ3179410

Akim Demaille

Publication date: 21 December 2016

Published in: Theoretical Aspects of Computing – ICTAC 2016 (Search for Journal in Brave)

Abstract: We present an algorithm to build an automaton from a rational expression. This approach introduces support for extended weighted expressions. Inspired by derived-term based algorithms, its core relies on a different construct, rational expansions. We introduce an inductive algorithm to compute the expansion of an expression from which the automaton follows. This algorithm is independent of the size of the alphabet, and actually even supports infinite alphabets. It can easily be accommodated to generate deterministic (weighted) automata. These constructs are implemented in Vcsn, a free-software platform dedicated to weighted automata and rational expressions.

Full work available at URL: https://arxiv.org/abs/1605.01530

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Implementation Concepts in Vaucanson 2
• THE ABSTRACT THEORY OF AUTOMATA
• Derivatives of Regular Expressions
• Partial derivatives of regular expressions and finite automaton constructions
• Behavioural differential equations: a coinductive calculus of streams, automata, and power series
• A Unified Construction of the Glushkov, Follow, and Antimirov Automata
• A play on regular expressions
• Derivatives of rational expressions with multiplicity
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Regular-expression derivatives re-examined
• Partial Derivatives of an Extended Regular Expression
• From Mirkin's prebases to Antimirov's word partial derivatives
• On the number of broken derived terms of a rational expression
• Derived-Term Automata of Multitape Rational Expressions
• An Efficient Computation of the Equation $\mathbb{K}$ -Automaton of a Regular $\mathbb{K}$ -Expression

Cited In (1)

• Derived-Term Automata of Multitape Rational Expressions

Uses Software

• Vaucanson

This page was built for publication: Derived-Term Automata for Extended Weighted Rational Expressions

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