A geometrical view of the determinization and minimization of finite-state automata

DOI10.1007/BF02090394zbMath0722.68080MaRDI QIDQ3210193

Andreas Podelski, Damian Niwinski, Bruno Courcelle

Publication date: 1991

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

minimizationdeterminizationtree automatonfinite-state wordrecognizability in algebraic structuresrectangular decompositions of relations

Mathematics Subject Classification ID

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

Related Items

EFFICIENT DETERMINISTIC FINITE AUTOMATA SPLIT-MINIMIZATION DERIVED FROM BRZOZOWSKI'S ALGORITHM, Polynomial inference of universal automata from membership and equivalence queries, On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes, An algebraic characterization of frontier testable tree languages, ENUMERATING NONDETERMINISTIC AUTOMATA FOR A GIVEN LANGUAGE WITHOUT CONSTRUCTING THE CANONICAL AUTOMATON, On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's, Descriptional complexity of regular languages, A Congruence-Based Perspective on Finite Tree Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-state \(\omega\)-languages
• A syntactic congruence for rational \(\omega\)-languages
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Linear Automaton Transformations
• Algebraic automata and context-free sets