Using Automata to obtain Regular Expressions for Induced Actions

1999/06/23 by Anne Heyworth, Heyworth, Anne
Computer Science · Mathematics · #08A50 16B50 68Q40 68Q42 68Q45 #Combinatorics (math.CO) #FOS: Mathematics #Formal Methods in Verification #Software Testing and Debugging Techniques #math.CO #msc:08A50 #msc:16B50 #msc:68Q40 #msc:68Q42 #msc:68Q45 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/9906153

14 pages, LaTeX2e, (submitted to IJAC)

arxiv created 1999/06/23 · openalex publication_date 1999/06/23 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Presentations of Kan extensions of category actions provide a natural framework for expressing induced actions, and therefore a range of different combinatorial problems. Rewrite systems for Kan extensions have been defined and a variation on the Knuth-Bendix completion procedure can be used to complete them -- when possible. Regular languages and automata are a useful way of expressing sets and actions, and in this paper we explain how to use rewrite systems for Kan extensions to construct automata expressing the induced action and how sets of normal forms can be calculated by obtaining language equations from the automata.

Related

• Using Rewriting Systems to Compute Kan Extensions and Induced Actions of Categories
• Rewriting Procedures Generalise to Kan Extensions of Actions of Categories
• Applications of Rewriting Systems and Groebner Bases to Computing Kan Extensions and Identities Among Relations
• Grobner Basis Techniques for Computing Actions of K-Categories
• A unified implementation of automata and expression structures, and of the associated algorithms using enriched categories