Minimal automaton for a factorial, transitive, and rational language

DOI10.1016/0304-3975(89)90022-4MaRDI QIDQ1822985zbMATH OpenOpenAlexFDO

Authors Danièle Beauquier

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0304-3975(89)90022-4

zbMATH Keywords

finite automatasyntactic monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Review text

A language is factorial if it contains all factors (i.e., subwords) of its words, and it is transitive if for any pair u, v of its words there exists a word w such that uwv is also in the language. A factorial, transitive, rational language is called an FTR-language. These languages can also be characterized as the languages recognizable by certain special finite automata for which the abbreviation ida is used. The author shows that every FTR-language has a minimal ida. Moreover, three ways of obtaining this minimal ida are presented.

Recommendations

• scientific article; zbMATH DE number 826075
• scientific article; zbMATH DE number 1222602
• scientific article; zbMATH DE number 4035189
• La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time)
• Deciding WQO for factorial languages

Cites work

• scientific article; zbMATH DE number 3911734 (Why is no real title available?)
• scientific article; zbMATH DE number 3911741 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 4035189 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• Sofic systems and graphs

Cited in

(10)

• Sofic shifts with synchronizing presentations
• The size of power automata.
• A hierarchy of shift equivalent sofic shifts
• A categorical invariant of flow equivalence of shifts
• A new algebraic invariant for weak equivalence of sofic subshifts
• Zeta Functions of Formal Languages
• THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE
• CONJUGACY INVARIANTS OF SUBSHIFTS: AN APPROACH FROM PROFINITE SEMIGROUP THEORY
• REDUCED POWER AUTOMATA AND SOFIC SYSTEMS
• Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts.

This page was built for publication: Minimal automaton for a factorial, transitive, and rational language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822985)