State complexity and the monoid of transformations of a finite set
From MaRDI portal
Abstract: In this paper we consider the state complexity of an operation on formal languages, root(L). This naturally entails the discussion of the monoid of transformations of a finite set. We obtain good upper and lower bounds on the state complexity of root(L) over alphabets of all sizes.
Recommendations
Cited in
(13)- State transitions as morphisms for complete lattices
- Syntactic complexity of suffix-free languages
- Complexity of suffix-free regular languages
- Complexity Analysis: Transformation Monoids of Finite Automata
- Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
- scientific article; zbMATH DE number 7453075 (Why is no real title available?)
- New tools for state complexity
- Most complex non-returning regular languages
- STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
- Complexity of left-ideal, suffix-closed and suffix-free regular languages
- Complexity of proper prefix-convex regular languages
- Complexity of proper prefix-convex regular languages
- On deterministic finite automata and syntactic monoid size
This page was built for publication: State complexity and the monoid of transformations of a finite set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463982)