2025/06/17 by John M. Campbell, Campbell, John M.
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q45 #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2506.14072
openalex publication_date 2025/06/17 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
Deterministic Finite Automata (DFAs) are of central importance in automata theory. In view of how state diagrams for DFAs are defined using directed graphs, this leads us to introduce a generalization of DFAs related to a method widely used in graph theory referred to as the discharging method. Given a DFA (Q, Σ, δ, q0, F), the transition function δ\colon Q × Σ→ Q determines a directed path in the corresponding state diagram based on an input string a1 a2 ⋯ an consisting of characters in Σ, and our generalization can be thought of as being based on how each vertex in D ''discharges'' rational values to adjacent vertices (by analogy with the discharging method) depending on the string a1 a2 ⋯ an and according to a fixed set of rules. We formalize this notion and pursue an exploration of the notion of a Discharging Deterministic Finite Automaton (DDFA) introduced in this paper. Our DDFA construction gives rise to a ring structure consisting of sequences that we refer to as being quasi-k-regular, and this ring generalizes the ring of k-regular sequences introduced by Allouche and Shallit.