A multi-parameter analysis of hard problems on deterministic finite automata
From MaRDI portal
Publication:2256724
DOI10.1016/j.jcss.2014.12.027zbMath1320.68090OpenAlexW2053159775MaRDI QIDQ2256724
Henning Fernau, Pinar Heggernes, Yngve Villanger
Publication date: 20 February 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2014.12.027
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (10)
Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Learning from positive and negative examples: dichotomies and parameterized algorithms ⋮ Learning from positive and negative examples: new proof for binary alphabets ⋮ On the complexity of automatic complexity ⋮ Fine-grained complexity of safety verification ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ On the Complexity of Bounded Context Switching. ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The tractability frontier for NFA minimization
- Descriptional and computational complexity of finite automata -- a survey
- Exact exponential algorithms.
- Parameterizing by the number of numbers
- On families of categorial grammars of bounded value, their learnability and related complexity questions
- The road coloring problem
- On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]]
- Parameterized learnability of juntas
- On the computational complexity of approximating distributions by probabilistic automata
- Which problems have strongly exponential complexity?
- Approximating the minimum length of synchronizing words is hard
- Polynomial complete problems in automata theory
- The Turing way to parameterized complexity
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- The NP-completeness of the road coloring problem
- Facility location problems: a parameterized view
- Inference of regular languages using state merging algorithms with search
- Parametrized complexity theory.
- Model-based testing of reactive systems. Advanced lectures.
- P–NP Threshold for Synchronizing Road Coloring
- Algorithmic construction of sets for k -restrictions
- The Parameterized Complexity of Chosen Problems for Finite Automata on Trees
- COMPAS - A Computing Package for Synchronization
- Approximating Minimum Reset Sequences
- Modifying the Upper Bound on the Length of Minimal Synchronizing Word
- Parameterized Complexity Results for 1-safe Petri Nets
- An Algorithm for Road Coloring
- Reflections on Multivariate Algorithmics and Problem Parameterization
- A threshold of ln n for approximating set cover
- Regular Inference as Vertex Coloring
- Reset Sequences for Monotonic Automata
- Synchronizing Automata and the Černý Conjecture
- The Complexity of Finding Reset Words in Finite Automata
- Exact DFA Identification Using SAT Solvers
- Learning Minimal Separating DFA’s for Compositional Verification
- Genetic Algorithm for Synchronization
- The Complexity of Satisfiability of Small Depth Circuits
- The minimum consistent DFA problem cannot be approximated within any polynomial
- Complexity of automaton identification from given data
- On the complexity of minimum inference of regular sets
- Cryptographic limitations on learning Boolean formulae and finite automata
- Computation Models for Parameterized Complexity
- A Multivariate Analysis of Some DFA Problems
- Remarks on Separating Words
- Testing finite-state machines: state identification and verification
- On a question of Eggan
- Language identification in the limit
- An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
- Efficient algorithms for the inference of minimum size DFAs
This page was built for publication: A multi-parameter analysis of hard problems on deterministic finite automata
