2021/08/29 by Alexsander A. de Melo, Alexsander Andrade de Melo, de Melo, Alexsander Andrade +2
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #cs.CC #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.12751
41 pages. This is an extended version of a paper with the same title that appeared at CSR 2020
arxiv created 2021/08/29 · openalex publication_date 2021/08/29 · arxiv updated 2021/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Traditionally, finite automata theory has been used as a framework for the representation of possibly infinite sets of strings. In this work, we introduce the notion of second-order finite automata, a formalism that combines finite automata with ordered decision diagrams, with the aim of representing possibly infinite \em sets of sets of strings. Our main result states that second-order finite automata can be canonized with respect to the second-order languages they represent. Using this canonization result, we show that sets of sets of strings represented by second-order finite automata are closed under the usual Boolean operations, such as union, intersection, difference and even under a suitable notion of complementation. Additionally, emptiness of intersection and inclusion are decidable. We provide two algorithmic applications for second-order automata. First, we show that several width/size minimization problems for deterministic and nondeterministic ODDs are solvable in fixed-parameter tractable time when parameterized by the width of the input ODD. In particular, our results imply FPT algorithms for corresponding width/size minimization problems for ordered binary decision diagrams (OBDDs) with a fixed variable ordering. Previously, only algorithms that take exponential time in the size of the input OBDD were known for width minimization, even for OBDDs of constant width. Second, we show that for each k and w one can count the number of distinct functions computable by ODDs of width at most w and length k in time h(|Σ|,w)⋅ kO(1), for a suitable h:ℕ× ℕ→ ℕ. This improves exponentially on the time necessary to explicitly enumerate all such functions, which is exponential in both the width parameter w and in the length k of the ODDs.