On the Computational Complexity of Partial Word Automata Problems
From MaRDI portal
Publication:4589235
DOI10.3233/FI-2016-1435zbMATH Open1380.68226OpenAlexW2563201274MaRDI QIDQ4589235FDOQ4589235
Authors: Markus Holzer, Sebastian Jakobi, Matthias Wendlandt 
Publication date: 9 November 2017
Published in: Fundamenta Informaticae (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3233/fi-2016-1435
Recommendations
- scientific article; zbMATH DE number 1701356
- DNA Computing
- On the computational complexity of P automata
- State complexity of partial word finite automata
- Complexity of problems concerning reset words for some partial cases of automata
- On the state complexity of partial word DFAs
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- On the Complexity of Deciding Avoidability of Sets of Partial Words
- On the complexity of deciding avoidability of sets of partial words
- Automata on Words
Cited In (16)
- On the state complexity of partial word DFAs
- Minimal partial languages and automata
- Regular languages of partial words
- Partial word DFAs
- State complexity of finite partial languages
- On the complexity of universality for partially ordered NFAs
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- On the computational complexity of P automata
- Minimal partial languages and automata
- Hard counting problems for partial words
- State complexity of finite partial languages
- Connecting partial words and regular languages
- Title not available (Why is that?)
- Computational and proof complexity of partial string avoidability
- The hardness of counting full words compatible with partial words
- State complexity of partial word finite automata
This page was built for publication: On the Computational Complexity of Partial Word Automata Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589235)
