Standard Sturmian words and automata minimization algorithms

DOI10.1016/j.tcs.2015.07.023zbMath1329.68159OpenAlexW915075976MaRDI QIDQ496057

Marinella Sciortino, Giuseppa Castiglione

Publication date: 16 September 2015

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.023

zbMATH Keywords

automata minimizationBrzozowski's minimization algorithmstandard Sturmian words

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (1)

Flexibility of the pressure function

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial double reversal minimization algorithm for deterministic finite automata
• Characteristic Sturmian words are extremal for the critical factorization theorem
• Circular Sturmian words and Hopcroft's algorithm
• Sturmian trees
• Burrows-Wheeler transform and Sturmian words
• A linear time solution to the single function coarsest partition problem
• Some combinatorial properties of Sturmian words
• Characterisations of balanced words via orderings
• On extremal cases of Hopcroft's algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Words, Trees and Automata Minimization
• EFFICIENT DETERMINISTIC FINITE AUTOMATA SPLIT-MINIMIZATION DERIVED FROM BRZOZOWSKI'S ALGORITHM
• Hopcroft's algorithm and tree-like automata
• A Challenging Family of Automata for Classical Minimization Algorithms
• On Christoffel classes
• Hopcroft’s Algorithm and Cyclic Automata
• Theory of Átomata
• Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
• Suffix Automata and Standard Sturmian Words
• Implementation and Application of Automata

This page was built for publication: Standard Sturmian words and automata minimization algorithms