Lower bound for the number of states of purposeful deterministic automata

MaRDI QIDQ796993zbMATHFDO

Authors A. N. Bojko

Publication date 1984

Published in Problems of Information Transmission (Search for Journal in Brave)

zbMATH Keywords

Moore automatacomplexity of deterministic expedient automatahomogeneous Markov media

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Lower bounds on the area of finite-state machines
• A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata
• On the number of active states in deterministic and nondeterministic finite automata
• On the Average Number of States of Partial Derivative Automata
• Towards exact state complexity bounds for input-driven pushdown automata
• A lower bound technique for the size of nondeterministic finite automata
• On the number of accepting states of finite automata
• A note on limited pushdown alphabets in stateless deterministic pushdown automata
• A lower bound for probabilistic algorithms for finite state machines
• Lower bound methods for the size of nondeterministic finite automata revisited

Cited in

(1)

• Lower bounds on the area of finite-state machines

This page was built for publication: Lower bound for the number of states of purposeful deterministic automata

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