On two Combinatorial Problems Arising from Automata Theory

DOI10.1016/S0304-0208(08)73432-7zbMATH Open0523.68042MaRDI QIDQ3674065FDOQ3674065

Publication date: 1983

Published in: Combinatorial Mathematics, Proceedings of the International Colloquium on Graph Theory and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

coding word length triangle conjecture rank of a word

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Algebraic theory of languages and automata (68Q70)

Cited In (78)

On the length of uncompletable words in unambiguous automata
Games with Opacity Condition
Synchronizing Automata on Quasi-Eulerian Digraph
Synchronizing automata with coinciding cycles
Title not available (Why is that?)
Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach
Fast synchronization of inhomogenous random automata
Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices
Synchronizing words under \textsf{LTL} constraints
On the smallest synchronizing terms of finite tree automata
The Synchronizing Probability Function for Primitive Sets of Matrices
Synchronizing automata with a letter of deficiency 2
ON THE LOCAL INVERTIBILITY OF FINITE STATE INFORMATION LOSSLESS AUTOMATA
Les automates circulaires biaisés vérifient la conjecture de Černý
Synchronization problems in automata without non-trivial cycles
Extremal Binary PFAs with Small Number of States
Title not available (Why is that?)
Circular automata synchronize with high probability
Strongly transitive automata and the Černý conjecture
Genetic Algorithm for Synchronization
Shortest synchronizing strings for Huffman codes
Inequalities for two set systems with prescribed intersections
Representation theory of finite semigroups, semigroup radicals and formal language theory
Modifying the upper bound on the length of minimal synchronizing word
A lower bound for the length of the shortest carefully synchronizing words
Experimental study of the shortest reset word of random automata
Extremal binary PFAs in a Černý family
Finding DFAs with Maximal Shortest Synchronizing Word Length
A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number
Synchronizing Automata over Nested Words
Improved upper bounds on synchronizing nondeterministic automata
Complexity of problems concerning reset words for cyclic and Eulerian automata
Title not available (Why is that?)
Sync-maximal permutation groups equal primitive permutation groups
On the Interplay Between Černý and Babai’s Conjectures
On the Synchronizing Probability Function and the Triple Rendezvous Time
Černý's conjecture and group representation theory
Strong Inapproximability of the Shortest Reset Word
Algebraic synchronization criterion and computing reset words
Synchronizing finite automata with short reset words
Synchronizing Automata Preserving a Chain of Partial Orders
Strongly connected synchronizing automata and the language of minimal reset words
Slowly synchronizing automata with fixed alphabet size
Synchronizing Automata of Bounded Rank
Synchronizing automata preserving a chain of partial orders
Ideal regular languages and strongly connected synchronizing automata
A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
Matchings and covers in hypergraphs
Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
Primitive groups, graph endomorphisms and synchronization
Synchronizing generalized monotonic automata
Approximating minimum reset sequences
Černý's conjecture and the road colouring problem
Synchronizing times for \(k\)-sets in automata
Synchronizing finite automata on Eulerian digraphs.
The Černý conjecture and 1-contracting automata
The Černý conjecture for one-cluster automata with prime length cycle
Primitive Sets of Nonnegative Matrices and Synchronizing Automata
Experiments with Synchronizing Automata
Using SAT solvers for synchronization issues in non-deterministic automata
Synchronizing Automata and the Černý Conjecture
Some contributions to the theory of transformation monoids
On the synchronizing probability function and the triple rendezvous time for synchronizing automata
Title not available (Why is that?)
Complexity of problems concerning reset words for cyclic and Eulerian automata
Geometrical solution of an intersection problem for two hypergraphs
Weakly saturated hypergraphs and a conjecture of Tuza
COMPAS -- a computing package for synchronization
Shortest Synchronizing Strings for Huffman Codes
Synchronizing Almost-Group Automata
Primitive digraphs with large exponents and slowly synchronizing automata
Synchronizing random automata on a 4-letter alphabet
Synchronizing series-parallel deterministic finite automata with loops and related problems
The road coloring problem
Lower Bounds for Synchronizing Word Lengths in Partial Automata
An Extremal Series of Eulerian Synchronizing Automata

This page was built for publication: On two Combinatorial Problems Arising from Automata Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3674065)