Operads, quasiorders, and regular languages

DOI10.1016/J.AAM.2016.01.002zbMATH Open1351.68173arXiv1401.2010OpenAlexW1777648780MaRDI QIDQ256333FDOQ256333

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)

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.

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

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

zbMATH Keywords

multi-tildeoperadquasiorderregular language

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Combalgebraic structures on decorated cliques
• Title not available (Why is that?)
• Some combinatorial operators in language theory
• Operads of decorated cliques. I: Construction and quotients
• Title not available (Why is that?)

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)