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 compositionsMany-valued truth-functionsSynchronizable automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Many-valued logic (03B50)

Related Items (20)

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

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

This page was built for publication: Composition sequences for functions over a finite domain.