Lengths of words accepted by nondeterministic finite automata

DOI10.1016/j.ipl.2020.105993zbMath1461.68104arXiv1802.04708OpenAlexW3038444735MaRDI QIDQ2203588

Aaron Potechin, Jeffrey O. Shallit

Publication date: 7 October 2020

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityfinite automatontheory of computationformal languagestrong exponential-time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (5)

Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices ⋮ On the Complexity of String Matching for Graphs ⋮ Unnamed Item ⋮ Two-dimensional pattern matching against local and regular-like picture languages ⋮ Wheeler languages

Cites Work

• Unnamed Item
• Unnamed Item
• Finding and counting given length cycles
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A Second Course in Formal Languages and Automata Theory
• Finding a Minimum Circuit in a Graph
• Color-coding
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Finding orthogonal vectors in discrete structures

This page was built for publication: Lengths of words accepted by nondeterministic finite automata