Automata in SageMath -- combinatorics meet theoretical computer science

MaRDI QIDQ2965981zbMATH OpenFDO

Authors Clemens Heuberger, Daniel Krenn, Sara Kropf

Publication date 3 March 2017

Full work available at URL https://arxiv.org/abs/1404.7458, https://dmtcs.episciences.org/1475/par

zbMATH Keywords

automatonHamming weightnon-adjacent formtransducertutorial

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Symbolic computation and algebraic computation (68W30)

Abstract: The new finite state machine package in the mathematics software system SageMath is presented and illustrated by many examples. Several combinatorial problems, in particular digit problems, are introduced, modeled by automata and transducers and solved using SageMath. In particular, we compute the asymptotic Hamming weight of a non-adjacent-form-like digit expansion, which was not known before.

Recommendations

• Applications of the finite state automata in the enumerative combinatorics
• scientific article; zbMATH DE number 4004253
• Automata methods in transcendence
• A symbolic finite-state approach for automated proving of theorems in combinatorial game theory
• Finite automata and arithmetic

Cited in

(4)

• Output sum of transducers: limiting distribution and periodic fluctuation
• Variances and covariances in the central limit theorem for the output of a transducer
• Application of Smirnov words to waiting time distributions of runs
• Analysis of carries in signed digit expansions

Describes a project that uses

Uses Software

• Mathematica
• OpenFst
• SageMath
• PyOpenFST
• SFST
• Vcsn
• ASTL
• FSA
• Python

This page was built for publication: Automata in SageMath -- combinatorics meet theoretical computer science

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