On two Combinatorial Problems Arising from Automata Theory
From MaRDI portal
Publication:3674065
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)
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
- COMPAS - A Computing Package for Synchronization
- A lower bound for the length of the shortest carefully synchronizing words
- 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
- Modifying the Upper Bound on the Length of Minimal Synchronizing 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
- Č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
- Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata
- 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?)
- Geometrical solution of an intersection problem for two hypergraphs
- Experimental Study of the Shortest Reset Word of Random Automata
- Weakly saturated hypergraphs and a conjecture of Tuza
- 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
- Approximating Minimum Reset Sequences
- 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)
