Extremal minimality conditions on automata

DOI10.1016/J.TCS.2012.03.049MaRDI QIDQ441884zbMATH OpenOpenAlexFDO

Authors Antonio Restivo, Roberto Vaglica

Publication date 8 August 2012

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

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

zbMATH Keywords

minimal automatadeterministic finite automataminimality problemstate-pair graph

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Dynamical aspects of cellular automata (37B15)

Recommendations

• Automata with Extremal Minimality Conditions
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Some remarks on automata minimality
• A graph theoretic approach to automata minimality
• Minimal NFA Problems are Hard

Cites work

• scientific article; zbMATH DE number 3943051 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1502109 (Why is no real title available?)
• scientific article; zbMATH DE number 1747444 (Why is no real title available?)
• A graph theoretic approach to automata minimality
• An Introduction to Symbolic Dynamics and Coding
• Automata with Extremal Minimality Conditions
• INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
• Multiple-entry finite automata
• Never minimal automata and the rainbow bipartite subgraph problem
• On the disjunctive set problem
• Slowly synchronizing automata and digraphs
• Some remarks on automata minimality
• Synchronised automata
• Syntactic complexity of ideal and closed languages

Cited in

(8)

• Primitivity, uniform minimality, and state complexity of Boolean operations
• A graph theoretic approach to automata minimality
• A maxmin problem on finite automata
• Closure properties of hyper-minimized automata
• Binary and circular automata having maximal state complexity for the set of synchronizing words
• Some remarks on automata minimality
• Never minimal automata and the rainbow bipartite subgraph problem
• Automata with Extremal Minimality Conditions

This page was built for publication: Extremal minimality conditions on automata

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