String execution time for finite languages: max is easy, min is hard

DOI10.1016/J.AUTOMATICA.2011.06.024MaRDI QIDQ642653zbMATH OpenOpenAlexFDO

Authors Rong Su, Gerhard J. Woeginger

Publication date 27 October 2011

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.automatica.2011.06.024

zbMATH Keywords

computational complexityfinite-state automatalanguages(max+) semiringheap models

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Max-plus and related algebras (15A80) Cellular automata (computational aspects) (68Q80) Hierarchical systems (93A13) Design techniques (robust design, computer-aided design, etc.) (93B51)

Recommendations

• Minimizing finite automata is computationally hard
• scientific article; zbMATH DE number 2040922
• scientific article; zbMATH DE number 2204051
• scientific article; zbMATH DE number 4108165
• scientific article; zbMATH DE number 4106272

Cites work

• scientific article; zbMATH DE number 4002104 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1163641 (Why is no real title available?)
• scientific article; zbMATH DE number 5018129 (Why is no real title available?)
• Performance evaluation of (max,+) automata
• Supervisory Control of a Class of Discrete Event Processes
• Supervisory control of \((\max,+)\) automata: a behavioral approach

Cited in

(5)

• New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems
• A weighted pair graph representation for reconstructibility of Boolean control networks
• Model approximation for batch flow shop scheduling with fixed batch sizes
• Analysis and control of max-plus linear discrete-event systems: an introduction
• Control protocol synthesis for multi-agent systems with similar actions instantiated from agent and requirement templates

This page was built for publication: String execution time for finite languages: max is easy, min is hard

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