Unary One Counter Net Problems

An intuitive definition of Unary Non-deterministic One Counter Nets (Unary OCN) via Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA) and Unary NFAs. A list of decision problems associated with automata, in particular Universality and (Compressed) Membership on Unary OCNs with examples and the current best known upper and lower computational complexity bounds. The potential for improvements on each bound for both Universality and Compressed Membership on Unary OCNs. Placement of my research in context of recent work and the position of Unary OCNs in the broader landscape of theoretical computer science.

FoCS Theory Workshop 2021

Henry Sinclair-Banks, 28/06/21, University of Warwick (UK).