Algebraic Theory of Automata and Languages
Group-matrix type automata are representations of strongly connected finite automata. The structure of these automata is studied through an investigation of the endomorphism monoids and automorphism groups. Classes of automata as partially ordered sets are studied and a kind of decomposition theory is developed. For the standard classes of regular and context-free languages the operations of insertion, scattered and ordinary deletion of substrings, shuffle as well as their closures are presented in up to 40 percent of the contents. The book collects and presents a number of old and new results on this subject. It is mathematically oriented, and gives no hints for applications. The contents is presented in eight chapters, shortly sketched as follows: Chapter 1 deals with the representations of strongly connected automata through automorphism groups. Chapter 2 generalizes the results from the preceeding Chapter to general automata. Chapter 3 considers sets of automata, partially ordered by homomorphisms. Chapter 4 presents results concerning the insertion and shuffle operations, while Chapter 5 determines the structure of commutative, regular shuffle closed languages. Chapter 6 is devoted to a detailed presentation of insertion and deletion operations, and Chapter 7 deals with the pair of shuffle and scattered deletion. The final Chapter 8 presents the so-called directable automata. References and a small index, not containing all relevant notions finish the 199 pages.
- scientific article; zbMATH DE number 3390671
- scientific article; zbMATH DE number 3250570
- Automata and algebraicity
- Algebraic structures of automata
- Automata algebras
- scientific article; zbMATH DE number 45581
- Automata and languages. Theory and applications
- Automata on algebraic structures
- scientific article; zbMATH DE number 3238653
- Automata in algebra
- Languages, D0L-systems, sets of curves, and surface automorphisms.
- Word problems of groups: formal languages, characterizations and decidability
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Shuffles of trees
- Regularity conditions for iterated shuffle on commutative regular languages
- The commutative closure of shuffle languages over group languages is regular
- Interval type-2 fuzzy automata and interval type-2 fuzzy grammar
- Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages
- Careful synchronization of partial deterministic finite automata
- Slowly synchronizing automata with zero and noncomplete sets
- Using SAT solvers for synchronization issues in non-deterministic automata
- Synchronization of automata with one undefined or ambiguous transition
- Duplication in DNA Sequences
- On Regularity-Preservation by String-Rewriting Systems
- Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory
- scientific article; zbMATH DE number 3909765 (Why is no real title available?)
- Products of automata
- Tree shuffle
- Monoid-matrix type automata
- scientific article; zbMATH DE number 45581 (Why is no real title available?)
- A bialgebraic approach to automata and formal language theory
- Representations of commutative asynchronous automata
- Algebraic structures of automata
- The length of subset reachability in nondeterministic automata
- On shuffling a word with its letter-to-letter substitution
- Lattice structures of automata
- Multi-wave soliton automata
- Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
- Set systems: order types, continuous nondeterministic deformations, and quasi-orders
- State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
- Determinism and simulation of soliton automata
- Cascade connections and triangular products of linear automata
- A lower bound for the length of the shortest carefully synchronizing words
- Languages generated by iterated idempotency
- On structure and representations of cyclic automata
This page was built for publication: Algebraic Theory of Automata and Languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4826930)