Complexity of road coloring with prescribed reset words (Q2424693): Difference between revisions

Latest revision as of 16:07, 19 July 2024

scientific article; zbMATH DE number 6566775

Complexity of Road Coloring with Prescribed Reset Words

Language	Label	Description	Also known as
English	Complexity of road coloring with prescribed reset words	scientific article; zbMATH DE number 6566775	Complexity of Road Coloring with Prescribed Reset Words

Statements

instance of

scholarly article

0 references

title

Complexity of road coloring with prescribed reset words (English)

0 references

Complexity of Road Coloring with Prescribed Reset Words (English)

0 references

0 references

0 references

Journal of Computer and System Sciences

0 references

Language and Automata Theory and Applications

0 references

publication date

25 June 2019

0 references

8 April 2016

0 references

full work available at URL

https://arxiv.org/abs/1412.0799

0 references

zbMATH Keywords

synchronizing word

0 references

reset word

0 references

road-coloring problem

0 references

synchronizing automata

0 references

Černý conjecture

0 references

algorithms on automata and words

0 references

road-coloring theorem

0 references

describes a project that uses

TESTAS

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Equivalence of topological Markov shifts

0 references

A complete solution to the complexity of synchronizing road coloring for non-binary alphabets

0 references

P–NP Threshold for Synchronizing Road Coloring

0 references

The complexity of satisfiability problems

0 references

Q5249241

0 references

Q5509690

0 references

Reset Sequences for Monotonic Automata

0 references

Synchronizing finite automata with short reset words

0 references

Computing the shortest reset words of synchronizing automata

0 references

An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

0 references

Synchronizing automata preserving a chain of partial orders

0 references

Q5747408

0 references

Strong Inapproximability of the Shortest Reset Word

0 references

A quadratic algorithm for road coloring

0 references

An Algorithm for Road Coloring

0 references

On the Number of Synchronizing Colorings of Digraphs

0 references

A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM

0 references

Semigroups and the generalized road coloring problem

0 references

The road coloring problem

0 references

A Multivariate Analysis of Some DFA Problems

0 references

Identifiers

zbMATH Open document ID

1425.68236

0 references

1425.68235

0 references

DOI

10.1016/j.jcss.2016.05.009

0 references

10.1007/978-3-319-15579-1_12

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2424693

@@ Property / cites work @@
+Equivalence of topological Markov shifts
@@ Property / cites work: Equivalence of topological Markov shifts / rank @@
+Normal rank
@@ Property / cites work @@
+A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
+Normal rank
@@ Property / cites work @@
+P–NP Threshold for Synchronizing Road Coloring
@@ Property / cites work: P–NP Threshold for Synchronizing Road Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of satisfiability problems
@@ Property / cites work: The complexity of satisfiability problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q5249241
@@ Property / cites work: Q5249241 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5509690
@@ Property / cites work: Q5509690 / rank @@
+Normal rank
@@ Property / cites work @@
+Reset Sequences for Monotonic Automata
@@ Property / cites work: Reset Sequences for Monotonic Automata / rank @@
+Normal rank
@@ Property / cites work @@
+Synchronizing finite automata with short reset words
+Normal rank
@@ Property / cites work @@
+Computing the shortest reset words of synchronizing automata
+Normal rank
@@ Property / cites work @@
+An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
+Normal rank
@@ Property / cites work @@
+Synchronizing automata preserving a chain of partial orders
+Normal rank
@@ Property / cites work @@
+Q5747408
@@ Property / cites work: Q5747408 / rank @@
+Normal rank
@@ Property / cites work @@
+Strong Inapproximability of the Shortest Reset Word
+Normal rank
@@ Property / cites work @@
+A quadratic algorithm for road coloring
@@ Property / cites work: A quadratic algorithm for road coloring / rank @@
+Normal rank
@@ Property / cites work @@
+An Algorithm for Road Coloring
@@ Property / cites work: An Algorithm for Road Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+On the Number of Synchronizing Colorings of Digraphs
+Normal rank
@@ Property / cites work @@
+A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
+Normal rank
@@ Property / cites work @@
+Semigroups and the generalized road coloring problem
+Normal rank
@@ Property / cites work @@
+The road coloring problem
@@ Property / cites work: The road coloring problem / rank @@
+Normal rank
@@ Property / cites work @@
+A Multivariate Analysis of Some DFA Problems
@@ Property / cites work: A Multivariate Analysis of Some DFA Problems / rank @@
+Normal rank