On two Combinatorial Problems Arising from Automata Theory
From MaRDI portal
Publication:3674065
DOI10.1016/S0304-0208(08)73432-7zbMath0523.68042MaRDI QIDQ3674065
Publication date: 1983
Published in: Combinatorial Mathematics, Proceedings of the International Colloquium on Graph Theory and Combinatorics (Search for Journal in Brave)
Combinatorial aspects of partitions of integers (05A17) Algebraic theory of languages and automata (68Q70) Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10)
Related Items (78)
Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ Weakly saturated hypergraphs and a conjecture of Tuza ⋮ Extremal binary PFAs in a Černý family ⋮ Shortest synchronizing strings for Huffman codes ⋮ Inequalities for two set systems with prescribed intersections ⋮ Synchronizing automata preserving a chain of partial orders ⋮ Strongly connected synchronizing automata and the language of minimal reset words ⋮ Using SAT solvers for synchronization issues in non-deterministic automata ⋮ The Černý conjecture and 1-contracting automata ⋮ Unnamed Item ⋮ A lower bound for the length of the shortest carefully synchronizing words ⋮ Synchronizing Automata on Quasi-Eulerian Digraph ⋮ Synchronizing Automata of Bounded Rank ⋮ Ideal regular languages and strongly connected synchronizing automata ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Synchronizing times for \(k\)-sets in automata ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Synchronizing random automata on a 4-letter alphabet ⋮ Synchronizing automata with a letter of deficiency 2 ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Synchronizing automata with coinciding cycles ⋮ Synchronizing Automata Preserving a Chain of Partial Orders ⋮ On the length of uncompletable words in unambiguous automata ⋮ Synchronizing finite automata on Eulerian digraphs. ⋮ Primitive groups, graph endomorphisms and synchronization ⋮ Synchronizing words under \textsf{LTL} constraints ⋮ Extremal Binary PFAs with Small Number of States ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Fast synchronization of inhomogenous random automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the smallest synchronizing terms of finite tree automata ⋮ Complexity of problems concerning reset words for cyclic and Eulerian automata ⋮ Les automates circulaires biaisés vérifient la conjecture de Černý ⋮ Some contributions to the theory of transformation monoids ⋮ Lower Bounds for Synchronizing Word Lengths in Partial Automata ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Synchronizing Automata and the Černý Conjecture ⋮ Circular automata synchronize with high probability ⋮ ON THE LOCAL INVERTIBILITY OF FINITE STATE INFORMATION LOSSLESS AUTOMATA ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ Finding DFAs with Maximal Shortest Synchronizing Word Length ⋮ Synchronizing generalized monotonic automata ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ Černý's conjecture and group representation theory ⋮ Shortest Synchronizing Strings for Huffman Codes ⋮ The Černý conjecture for one-cluster automata with prime length cycle ⋮ Improved upper bounds on synchronizing nondeterministic automata ⋮ Algebraic synchronization criterion and computing reset words ⋮ Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata ⋮ Experimental Study of the Shortest Reset Word of Random Automata ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ The road coloring problem ⋮ Representation theory of finite semigroups, semigroup radicals and formal language theory ⋮ Genetic Algorithm for Synchronization ⋮ COMPAS - A Computing Package for Synchronization ⋮ Approximating Minimum Reset Sequences ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Synchronizing finite automata with short reset words ⋮ Synchronizing Automata over Nested Words ⋮ Synchronization problems in automata without non-trivial cycles ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Modifying the Upper Bound on the Length of Minimal Synchronizing Word ⋮ Matchings and covers in hypergraphs ⋮ A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata ⋮ Experiments with Synchronizing Automata ⋮ Games with Opacity Condition ⋮ Černý's conjecture and the road colouring problem ⋮ Strongly transitive automata and the Černý conjecture ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ The Synchronizing Probability Function for Primitive Sets of Matrices ⋮ Synchronizing Almost-Group Automata ⋮ Geometrical solution of an intersection problem for two hypergraphs ⋮ Unnamed Item ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems
This page was built for publication: On two Combinatorial Problems Arising from Automata Theory
