Optimal state reductions of automata with partially specified behaviors

DOI10.1016/j.tcs.2016.05.002zbMath1355.68167OpenAlexW2350842303WikidataQ61677486 ScholiaQ61677486MaRDI QIDQ728283

Rogério Reis, Giovanni Pighizzini, Nelma Moreira

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

finite automatanondeterminismdescriptional complexitydon't care automata

Mathematics Subject Classification ID

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

Related Items (3)

Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures ⋮ State complexity of binary coded regular languages ⋮ State complexity of binary coded regular languages

Cites Work

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

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