
On the Width of Regular Classes of Finite Structures
In this work, we introduce the notion of decisional width of a finite re...
read it

Finite Automata Intersection NonEmptiness: Parameterized Complexity Revisited
The problem DFAIntersectionNonemptiness asks if a given number of dete...
read it

On (colex) Ordering Automata
The states of a deterministic finite automaton A can be identified with ...
read it

Large Scale Geometries of Infinite Strings
We introduce geometric consideration into the theory of formal languages...
read it

On the Expressivity and Applicability of Model Representation Formalisms
A number of firstorder calculi employ an explicit model representation ...
read it

Outfixguided insertion
Motivated by work on biooperations on DNA strings, we consider an outfi...
read it

Fast Computations on Ordered Nominal Sets
We show how to compute efficiently with nominal sets over the total orde...
read it
SecondOrder Finite Automata
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 secondorder finite automata, a formalism that combines finite automata with ordered decision diagrams, with the aim of representing possibly infinite sets of sets of strings. Our main result states that secondorder finite automata can be canonized with respect to the secondorder languages they represent. Using this canonization result, we show that sets of sets of strings represented by secondorder 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 secondorder automata. First, we show that several width/size minimization problems for deterministic and nondeterministic ODDs are solvable in fixedparameter 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)· k^O(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.
READ FULL TEXT
Comments
There are no comments yet.