Synchronizing series-parallel deterministic finite automata with loops and related problems

DOI10.1051/ita/2021005OpenAlexW3186440523MaRDI QIDQ5021111

Henning Fernau, Jens Bruchertseifer

Publication date: 12 January 2022

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2021005

zbMATH Keywords

series-parallel graphsparameterized complexitysynchronizing words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class?

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
• Series parallel digraphs with loops
• Fundamentals of parameterized complexity
• Complexity of problems concerning reset words for cyclic and Eulerian automata
• Parameterized complexity and approximability of the longest compatible sequence problem
• Complexity of a problem concerning reset words for Eulerian binary automata
• Synchronizing automata with finitely many minimal synchronizing words
• The Černý conjecture for one-cluster automata with prime length cycle
• Some consequences of non-uniform conditions on uniform classes
• Synchronizing automata preserving a chain of partial orders
• Are there any good digraph width measures?
• Languages of R-trivial monoids
• An extremal problem for two families of sets
• Parallel recognition of series-parallel graphs
• The parameterized complexity of sequence alignment and consensus
• On the parameterized complexity of short computation and factorization
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• On the synchronization of planar automata
• Approximating the minimum length of synchronizing words is hard
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Synchronizing words and monoid factorization: a parameterized perspective
• A multi-parameter analysis of hard problems on deterministic finite automata
• Modern aspects of complexity within formal languages
• Comparing linear width parameters for directed graphs
• Computing the shortest reset words of synchronizing automata
• Digraphs of bounded elimination width
• Model-based testing of reactive systems. Advanced lectures.
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• Digraphs of Bounded Width
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• On two Combinatorial Problems Arising from Automata Theory
• The Recognition of Series Parallel Digraphs
• Semicomputable points in Euclidean spaces
• An improvement to a recent upper bound for synchronizing words of finite automata
• Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
• Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata
• Analytical approach to parallel repetition
• Parameterized Algorithms
• Synchronization problems in automata without non-trivial cycles

This page was built for publication: Synchronizing series-parallel deterministic finite automata with loops and related problems