Operads, quasiorders, and regular languages

DOI10.1016/J.AAM.2016.01.002MaRDI QIDQ256333zbMATH OpenOpenAlexFDO

Authors Samuele Giraudo, Ludovic Mignot, Florent Nicart, Jean-Gabriel Luque

Publication date 9 March 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

multi-tildeoperadquasiorderregular language

Mathematics Subject Classification ID

Algebraic combinatorics (05E99) Algebraic theory of languages and automata (68Q70)

Abstract: We generalize the construction of multitildes in the aim to provide multitilde operators for regular languages. We show that the underliying algebraic structure involves the action of some operads. An operad is an algebraic structure that mimics the composition of the functions. The involved operads are described in terms of combinatorial objects. These operads are obtained from more primitive objects, namely precompositions, whose algebraic counter-parts are investigated. One of these operads acts faithfully on languages in the sense that two different operators act in two different ways.

Recommendations

• Some combinatorial operators in language theory
• Nonsymmetric operads in combinatorics
• Multi-tilde Operators and Their Glushkov Automata
• Operads and algebraic combinatorics of trees
• Quotients of the magmatic operad: lattice structures and convergent rewrite systems

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1757930 (Why is no real title available?)
• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• scientific article; zbMATH DE number 3028682 (Why is no real title available?)
• Acyclic automata and small expressions using multi-tilde-bar operators
• Algebraic operads
• Complexity measures for regular expressions
• Derivatives of Regular Expressions
• FROM C-CONTINUATIONS TO NEW QUADRATIC ALGORITHMS FOR AUTOMATON SYNTHESIS
• Multi-bar and multi-tilde regular operators
• Multi-tilde-bar expressions and their automata
• Partial derivatives of regular expressions and finite automaton constructions
• Some combinatorial operators in language theory
• THE ABSTRACT THEORY OF AUTOMATA
• The geometry of iterated loop spaces
• Three models for the description of language

Cited in

(5)

• Combalgebraic structures on decorated cliques
• scientific article; zbMATH DE number 1944129 (Why is no real title available?)
• Some combinatorial operators in language theory
• Operads of decorated cliques. I: Construction and quotients
• scientific article; zbMATH DE number 3557759 (Why is no real title available?)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Operads, quasiorders, and regular languages

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