Composition sequences for functions over a finite domain.

DOI10.1016/S0304-3975(01)00227-4zbMath1064.68058MaRDI QIDQ1853744

Arto Salomaa

Publication date: 22 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Length of compositions; Many-valued truth-functions; Synchronizable automata

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

03B50: Many-valued logic

Related Items

Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata, On the Interplay Between Černý and Babai’s Conjectures, Compositions of Functions and Permutations Specified by Minimal Reaction Systems, STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET, Complexity of problems concerning reset words for cyclic and Eulerian automata, On the state complexity of reversals of regular languages, The Černý conjecture for one-cluster automata with prime length cycle, Synchronizing automata preserving a chain of partial orders, Synchronizing automata with a letter of deficiency 2, Approximating the minimum length of synchronizing words is hard, Synchronizing generalized monotonic automata, Černý's conjecture and the road colouring problem, Preset Distinguishing Sequences and Diameter of Transformation Semigroups, Composition Sequences and Synchronizing Automata, THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE, Minimal Reaction Systems Defining Subset Functions, Undecidability of State Complexities Using Mirror Images, Synchronizing Automata Preserving a Chain of Partial Orders, Synchronizing Automata and the Černý Conjecture, On the Computational Complexity of Monotone Constraint Satisfaction Problems

Cites Work

• Reset words for commutative and solvable automata
• On the Length of the Smallest Uniform Experiment which Distinguishes the Terminal States of a Machine
• Reset Sequences for Monotonic Automata
• A theorem concerning the composition of functions of several variables ranging over a finite set
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item