检索结果-内蒙古大学图书馆

The NP-completeness of the road coloring problem

INFORMATION PROCESSING LETTERS 2011年第7期111卷 342-347页

作者： Roman, Adam Jagiellonian Univ Inst Comp Sci Krakow Poland

The road coloring problem (RCP) originates in [1 ] and it was stated explicitly in the paper by Adler et al. [2]. It can be formulated as follows: let C be a strongly connected, constant out-degree finite digraph such that the greatest common divisor (gcd) of the lengths of all cycles in C equals 1. Is there an edge labeling, turning C into a deterministic finite synchronizing automaton? The problem is of great importance in automata theory, because the synchronizing property makes the automaton behavior resistant to errors that could occur in an input word: after the error is detected, the synchronizing word can reset the automaton to its initial state, as if there were no error. In this way we regain the control over automaton action.

关键词： Computational complexity Synchronization road coloring problem

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON SYNCHRONIZED AUTOMATA AND road coloring problem

引用

International Journal of Foundations of Computer Science 2002年第3期13卷 459-471页

作者： KAREL CULIK, II JUHANI KARHUMÄKI JARKKO KARI Department of Computer Science University of South Carolina Columbia South Carolina 29208 USA Department of Mathematics and Turku Centre for Computer Science University of Turku FIN-20014 Turku Finland Department of Computer Science 14 MacLean Hall University of Iowa Iowa City Iowa 52242 USA Current address: Department of Mathematics University of Turku FIN-20014 Turku Finland

We consider the problem of labeling a directed multigraph so that it becomes a synchronized finite automaton, as an ultimate goal to solve the famous road coloring Conjecture, cf. [1,2]. We introduce a relabeling method which can be used for a large class of automata to improve their 'degree of synchronization'. This allows, for example, to formulate the conjecture in several equivalent ways.

关键词： Finite automata synchronization road coloring problem

来源：评论

学校读者我要写书评

暂无评论

Independent sets of words and the synchronization problem

引用

ADVANCES IN APPLIED MATHEMATICS 2013年第3期50卷 339-355页

作者： Carpi, Arturo D'Alessandro, Flavio Univ Perugia Dipartimento Matemat & Informat I-06123 Perugia Italy Univ Roma La Sapienza Dipartimento Matemat I-00185 Rome Italy Bogazici Univ Dept Math TR-34342 Istanbul Turkey

The synchronization problem is investigated for the class of locally strongly transitive automata introduced in Carpi and D'Alessandro (2009) [9]. Some extensions of this problem related to the notions of stable set and word of minimal rank of an automaton are studied. An application to synchronizing colorings of aperiodic graphs with a Hamiltonian path is also considered. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Cerny conjecture road coloring problem Synchronizing automaton

来源：评论

学校读者我要写书评

暂无评论

A quadratic algorithm for road coloring

引用

DISCRETE APPLIED MATHEMATICS 2014年 169卷 15-29页

作者： Beal, Marie-Pierre Perrin, Dominique Univ Paris Est Lab Informat Gaspard Monge CNRS UMR 8049 F-77454 Marne La Vallee France

The road coloring Theorem states that every aperiodic directed graph with constant outdegree has a synchronized coloring. This theorem had been conjectured during many years as the road coloring problem before being settled by A. ***'s proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the road coloring Theorem to the periodic case. (C) 2013 Elsevier B.V. All rights reserved.

关键词： road coloring problem Synchronized directed graphs Synchronization of automata

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of Synchronization and road coloring

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2015年第1期17卷 283-305页

作者： Vorel, Vojtech Roman, Adam Charles Univ Prague Fac Math & Phys Prague Czech Republic Jagiellonian Univ Inst Comp Sci Krakow Poland

First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.

关键词： synchronizing word reset word road coloring problem synchronizing automata parameterized complexity Cerny conjecture

来源：评论

学校读者我要写书评

暂无评论

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

引用

INFORMATION AND COMPUTATION 2015年 242卷 383-393页

作者： Roman, A. Drewienkowski, M. Jagiellonian Univ Inst Comp Sci PL-30348 Krakow Poland Ericpol Telecom PL-30348 Krakow Poland

The parameterized Synchronizing-road-coloring problem (in short: SRCPCl) in its decision version can be formulated as follows: given a digraph Gwith constant out-degree l, check if G can be synchronized by some word of length C for some synchronizing labeling. We consider the family {SRCPCl}(C, l) of problems parameterized with constants C and l and try to find for which C and l the problem SRCPCl is NP-complete. It is known that SRCPC3 is NP-complete for C >= 8. We improve this result by showing that it is so for C >= 4and for l >= 3. We also show that SRCPCl is in P for C <= 2and l >= 1. Finally, we solve the problem completely for the non-binary alphabets by showing that SRCP3l is in P for l >= 3. (C) 2015 Elsevier Inc. All rights reserved.

关键词： road coloring problem Synchronizing word Cerny conjecture Synchronizing automata Reset word

来源：评论

学校读者我要写书评

暂无评论

Complexity of road coloring with prescribed reset words

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2019年 104卷 342-358页

作者： Vorel, Vojtech Roman, Adam Charles Univ Prague Fac Math & Phys Malostranske Nam 25 Prague Czech Republic Jagiellonian Univ Inst Comp Sci Lojasiewicza 6 PL-30348 Krakow Poland

By the road coloring Theorem (Trahtman, 2008), the edges of any given aperiodic strongly connected directed multigraph with a constant out-degree can be colored such that the resulting automaton admits a reset word. There may also be a need for a particular reset word to be admitted. In this paper we consider the following problem: given a word w and digraph G, is it true that G has a coloring that is synchronized by w? We show that it is NP-complete for certain fixed words. For the binary alphabet we present a classification that separates such words from those that make the problem solvable in polynomial time. The classification differs if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Synchronizing word Reset word road coloring problem Synchronizing automata Cerny conjecture

来源：评论

学校读者我要写书评

暂无评论

REALIZATION OF AN ERGODIC MARKOV CHAIN AS A RANDOM WALK SUBJECT TO A SYNCHRONIZING road coloring

引用

JOURNAL OF APPLIED PROBABILITY 2011年第3期48卷 766-777页

作者： Yano, Kouji Yasutomi, Kenji Kyoto Univ Grad Sch Sci Sakyo Ku Kyoto 6068502 Japan Ritsumeikan Univ Shiga 5258577 Japan

An ergodic Markov chain is proved to be the realization of a random walk in a directed graph subject to a synchronizing road coloring. The result ensures the existence of appropriate random mappings in Propp-Wilson's coupling from the past. The proof is based on the road coloring theorem. A necessary and sufficient condition for approximate preservation of entropies is also given.

关键词： Markov chain random walk in a directed graph road coloring problem Tsirelson's equation coupling from the past

来源：评论

学校读者我要写书评

暂无评论

A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2011年第2期22卷 277-288页

作者： Beal, Marie-Pierre Berlinkov, Mikhail V. Perrin, Dominique Univ Paris Est CNRS Lab Informat Gaspard Monge F-77454 Marne La Vallee 2 France Ural State Univ Dept Algebra & Discrete Math Ekaterinburg 620083 Russia

Cerny's conjecture asserts the existence of a synchronizing word of length at most (n - 1)(2) for any synchronized n-state deterministic automaton. We prove a quadratic upper bound on the length of a synchronizing word for any synchronized n-state deterministic automaton satisfying the following additional property: there is a letter a such that for any pair of states p, q, one has p.a(r) = q.a(s) for some integers r, s (for a state p and a word w, we denote by p.w the state reached from p by the path labeled w). As a consequence, we show that for any finite synchronized prefix code with an n-state decoder, there is a synchronizing word of length O(n(2)). This applies in particular to Huffman codes.

关键词： Cerny's conjecture road coloring problem synchronized automata

来源：评论

学校读者我要写书评

暂无评论

The Synchronization problem for Locally Strongly Transitive Automata

引用

34th International Symposium on Mathematical Foundations of Computer Science

作者： Carpi, Arturo D'Alessandro, Flavio Univ Perugia Dipartimento Matemat & Informat Via Vanvitelli 1 I-06123 Perugia Italy Univ Rome Dipartimento Matemat Rome 00185 Italy

The synchronization problem is investigated for a new class of deterministic automata called locally strongly., transitive. An application to synchronizing colorings of aperiodic graphs with a cycle of prime length is... 详细信息

ISBN: (纸本)9783642038150

关键词： Cerny conjecture road coloring problem synchronizing automation rational series

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：