Optimal state reductions of automata with partially specified behaviors

DOI10.1016/J.TCS.2016.05.002MaRDI QIDQ728283zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Nelma Moreira, Giovanni Pighizzini, Rogério Reis

Publication date 19 December 2016

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

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

zbMATH Keywords

descriptional complexitydon't care automatafinite automatanondeterminism

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Optimal state reductions of automata with partially specified behaviors
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Minimal NFA Problems are Hard
• Hyper-minimizing minimized deterministic finite state automata
• scientific article; zbMATH DE number 176769

Cites work

• Chrobak normal form revisited, with applications
• Complexity of automaton identification from given data
• Don't care words with an application to the automata-based approach for real addition
• Finite automata and unary languages
• Learning Minimal Separating DFA’s for Compositional Verification
• Magic numbers in the state hierarchy of finite automata
• Minimal NFA Problems are Hard
• On cliques in graphs
• Optimal simulation of self-verifying automata by deterministic automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• State Reduction in Incompletely Specified Finite-State Machines
• Universal disjunctive concatenation and star

Cited in

(8)

• Don't care words with an application to the automata-based approach for real addition
• State complexity of binary coded regular languages
• Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures
• scientific article; zbMATH DE number 1213009 (Why is no real title available?)
• Optimal state reductions of automata with partially specified behaviors
• Don’t Care Words with an Application to the Automata-Based Approach for Real Addition
• On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words
• State complexity of binary coded regular languages

This page was built for publication: Optimal state reductions of automata with partially specified behaviors

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