We consider first-order logic over the subword ordering on finite words where each word is
available as a constant. Our first result is that the Σ 1 theory is undecidable (already over two …

We consider a general class of decision problems concerning formal languages, called
“(one-dimensional) unboundedness predicates”, for automata that feature reversal-bounded …

Parikh automata extend finite automata by counters that can be tested for membership in a
semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable …

We study logics expressing properties of paths in graphs that are tailored to querying graph
databases: a data model for new applications such as social networks, the Semantic Web …

Parikh automata extend finite automata by counters that can be tested for membership in a
semilinear set, but only at the end of a run, thereby preserving many of the desirable …

The regular separability problem asks, for two given languages, if there exists a regular
language including one of them but disjoint from the other. Our main result is decidability …

We investigate a subclass of languages recognized by vector addition systems, namely
languages of nondeterministic Parikh automata. While the regularity problem (is the …

Several variants of Parikh automata on infinite words were recently introduced by Guha et
al.[FSTTCS, 2022]. We show that one of these variants coincides with blind counter machine …

The Parikh finite word automaton model (PA) was introduced and studied by Klaedtke and
Rueß. Here, we present some expressiveness properties of a restriction of the deterministic …

A common problem in string constraint solvers is computing the Parikh image, a linear
arithmetic formula that describes all possible combinations of character counts in strings of a …