On the complexity of existence of homing sequences for nondeterministic finite state machines

DOI10.1134/S0361768814060140zbMath1339.68120OpenAlexW2022052039MaRDI QIDQ300305

F. Blanchet-Sadri, M. Dambrine

Publication date: 27 June 2016

Published in: Programming and Computer Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0361768814060140

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (1)

Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronizing generalized monotonic automata
• Polynomial complete problems in automata theory
• Relationships between nondeterministic and deterministic tape complexities
• Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines
• On the Length of Homing Sequences for Nondeterministic Finite State Machines

This page was built for publication: On the complexity of existence of homing sequences for nondeterministic finite state machines