most citedUniversal quantification makes automatic structures hard to decide

1 citations · 1 across the 4 of their papers we have counts for

collaborators
Showing cs.LOShow all

2 papers · 1 filter

cs.LO2026

Scoped MSO, Register Automata, and Expressions: Equivalence over Data Words

Radosław Piórkowski

This paper establishes logical and expression-based characterizations for the class of languages recognized by nondeterministic register automata with guessing (NRA) over infinite…

cs.LO2023★ 1 cited

Universal quantification makes automatic structures hard to decide

Christoph Haase, Radoslaw Piórkowski

Automatic structures are first-order structures whose universe and relations can be represented as regular languages. It follows from the standard closure properties of regular lan…