scientific article; zbMATH DE number 3222112
From MaRDI portal
Publication:5509690
zbMath0137.01101MaRDI QIDQ5509690
Publication date: 1964
Full work available at URL: https://eudml.org/doc/29801
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Synchronization of Parikh automata ⋮ Synchronizing automata with coinciding cycles ⋮ Synchronizing Boolean networks asynchronously ⋮ On the meeting of random walks on random DFA ⋮ Synchronizing words under \textsf{LTL} constraints ⋮ Normalish Amenable Subgroups of the R. Thompson Groups ⋮ Extremal Binary PFAs with Small Number of States ⋮ Fast synchronization of inhomogenous random automata ⋮ On the smallest synchronizing terms of finite tree automata ⋮ Estimation of the length of reset words for automata with simple idempotents ⋮ Reaching the minimum ideal in a finite semigroup ⋮ Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ Extremal binary PFAs in a Černý family ⋮ Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Cerny's conjecture for automata with simple idempotents ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Shortest synchronizing strings for Huffman codes ⋮ Synchronizing automata preserving a chain of partial orders ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Strongly connected synchronizing automata and the language of minimal reset words ⋮ The Černý conjecture and 1-contracting automata ⋮ Unnamed Item ⋮ Synchronizing Automata on Quasi-Eulerian Digraph ⋮ Synchronizing Automata of Bounded Rank ⋮ Synchronization of Automata with One Undefined or Ambiguous Transition ⋮ Ideal regular languages and strongly connected synchronizing automata ⋮ Representation of (Left) Ideal Regular Languages by Synchronizing Automata ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Constrained synchronization for monotonic and solvable automata and automata with simple idempotents ⋮ On synchronizing unambiguous automata ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Careful synchronization of partial deterministic finite automata ⋮ Synchronizing automata with a letter of deficiency 2 ⋮ Approximating the minimum length of synchronizing words is hard ⋮ Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata ⋮ Emergence on Decreasing Sandpile Models ⋮ On the Number of Synchronizing Colorings of Digraphs ⋮ Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata ⋮ Synchronizing Automata Preserving a Chain of Partial Orders ⋮ On the length of uncompletable words in unambiguous automata ⋮ Complexity of road coloring with prescribed reset words ⋮ A graph theoretic approach to automata minimality ⋮ On primitivity of sets of matrices ⋮ Synchronizing sequences for road colored digraphs ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Unnamed Item ⋮ Lifespan in a primitive Boolean linear dynamical system ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ Complexity of problems concerning reset words for cyclic and Eulerian automata ⋮ Preimage problems for deterministic finite automata ⋮ Recent results on syntactic groups of prefix codes. ⋮ Les automates circulaires biaisés vérifient la conjecture de Černý ⋮ Some contributions to the theory of transformation monoids ⋮ The Synchronization Problem for Strongly Transitive Automata ⋮ Image reducing words and subgroups of free groups. ⋮ Lower Bounds for Synchronizing Word Lengths in Partial Automata ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Synchronizing Automata and the Černý Conjecture ⋮ 2-Synchronizing Words ⋮ On Synchronizing Tree Automata and Their Work–Optimal Parallel Run, Usable for Parallel Tree Pattern Matching ⋮ Surface Dimension, Tiles, and Synchronizing Automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words ⋮ State complexity of the set of synchronizing words for circular automata and automata over binary alphabets ⋮ Constrained synchronization and commutativity ⋮ ON THE LOCAL INVERTIBILITY OF FINITE STATE INFORMATION LOSSLESS AUTOMATA ⋮ The complexity of synchronizing Markov decision processes ⋮ Algorithms for media ⋮ Synchronization ⋮ A series of slowly synchronizing automata with a zero state over a small alphabet ⋮ Černý conjecture for edge-colored digraphs with few junctions ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ On incomplete and synchronizing finite sets ⋮ A finite set of functions with an EXPTIME-complete composition problem ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Synchronizing generalized monotonic automata ⋮ Synchronizing monotonic automata ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ Synchronizing automata with finitely many minimal synchronizing words ⋮ Černý's conjecture and group representation theory ⋮ Computational complexity of synchronization under regular commutative constraints ⋮ Shortest Synchronizing Strings for Huffman Codes ⋮ The Černý conjecture for one-cluster automata with prime length cycle ⋮ Synchronizing groups and automata ⋮ Improved upper bounds on synchronizing nondeterministic automata ⋮ Algebraic synchronization criterion and computing reset words ⋮ Lower Bound for the Length of Synchronizing Words in Partially-Synchronizing Automata ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet ⋮ Representation theory of finite semigroups, semigroup radicals and formal language theory ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Simplicity of augmentation submodules for transformation monoids ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Extremal synchronizing circular automata ⋮ Matrix Mortality and the Černý-Pin Conjecture ⋮ Semicomputable points in Euclidean spaces ⋮ The Length of Subset Reachability in Nondeterministic Automata ⋮ Attainable Values of Reset Thresholds ⋮ Synchronizing words for real-time deterministic pushdown automata (extended abstract) ⋮ Unnamed Item ⋮ 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 ⋮ Existence of constants in regular splicing languages ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Reset complexity and completely reachable automata with simple idempotents ⋮ Computing the shortest reset words of synchronizing automata ⋮ Distributed graph problems through an automata-theoretic Lens
Cites Work
