Existential length universality

DOI10.4230/LIPICS.STACS.2020.16MaRDI QIDQ5874287zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Martin Lange, Narad Rampersad, Marek Szykuła, Jeffrey Shallit

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/1702.03961

zbMATH Keywords

decision problemdeterministic automatonnondeterministic automatonpushdown automatonregular expressionregular languageuniversality

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(7)

• Absent Subsequences in Words
• Matching patterns with variables under Simon's congruence
• k-universality of regular languages
• The edit distance to k-subsequence universality
• \(k\)-universality of regular languages
• The edit distance to \(k\)-subsequence universality
• The complexity of reachability problems in strongly connected finite automata

This page was built for publication: Existential length universality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874287)