Derived-term automata for extended weighted rational expressions

DOI10.1007/978-3-319-46750-4_20MaRDI QIDQ3179410zbMATH OpenOpenAlexFDO

Authors Akim Demaille

Publication date 21 December 2016

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

Recommendations

• Derived-term automata of multitape rational expressions
• Derived-term automata of weighted rational expressions with quotient operators
• FROM REGULAR WEIGHTED EXPRESSIONS TO FINITE AUTOMATA
• Derived-term automata of multitape expressions with composition
• LATIN 2004: Theoretical Informatics

Cites work

• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• A Unified Construction of the Glushkov, Follow, and Antimirov Automata
• A play on regular expressions: functional pearl
• An Efficient Computation of the Equation $\mathbb{K}$ -Automaton of a Regular $\mathbb{K}$ -Expression
• Behavioural differential equations: a coinductive calculus of streams, automata, and power series
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Derivatives of Regular Expressions
• Derivatives of rational expressions with multiplicity
• Derived-term automata of multitape rational expressions
• From Mirkin's prebases to Antimirov's word partial derivatives
• Implementation concepts in Vaucanson 2
• On the number of broken derived terms of a rational expression
• Partial derivatives of an extended regular expression
• Partial derivatives of regular expressions and finite automaton constructions
• Regular-expression derivatives re-examined
• THE ABSTRACT THEORY OF AUTOMATA

Cited in

(9)

• A type system for weighted automata and rational expressions
• Derived-term automata of multitape expressions with composition
• Derived-term automata of multitape rational expressions
• Implementation concepts in Vaucanson 2
• Derived-term automata of weighted rational expressions with quotient operators
• Non-deterministic finite cover automata
• Introducing VAUCANSON
• From Hadamard expressions to weighted rotating automata and back
• FROM REGULAR WEIGHTED EXPRESSIONS TO FINITE AUTOMATA

Describes a project that uses

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)