Conversion from OCA to Parikh-equivalent NFA requires a quasi-polynomial growth in description size. To prove this, we define and study a one-player game akin to pebbling.

Every one-counter automaton with n states accepts a word of length at most 14n², unless its language is empty.

If some variables in integer programs are quantified universally instead of existentially, then the decision problem becomes complete for the k-th level of the polynomial hierarchy, assuming k quantifier blocks.

LP relaxations of integer programs encoding set cover are useful for minimization of regular expressions and OR-circuits.

To measure how semilinear sets “grow” under Boolean operations, we keep track of the maximum norm of generators.

We propose a simple generalization of partial order dimension, with an application in software testing.

The downward and upward closure of one-counter languages have small NFA. So does the Parikh image if the alphabet has fixed size.

How many states does a {OCA, DPDA, Turing machine} need to have in order to accept the singleton language {aⁿ} ?

DPDA equivalence is in P for unary (singleton) input alphabet. This relies on algorithmics for grammar-compressed strings. Also, deciding if a CFG generates words of all lengths is Π₂P-complete.

Schützenberger’s construction for the uniformization of rational relations extends to nested words.