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

DOI10.1016/J.AUTOMATICA.2011.06.024zbMath1228.93005OpenAlexW2082516436MaRDI QIDQ642653

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

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

Related Items (5)

Control protocol synthesis for multi-agent systems with similar actions instantiated from agent and requirement templates ⋮ Analysis and control of max-plus linear discrete-event systems: an introduction ⋮ Model approximation for batch flow shop scheduling with fixed batch sizes ⋮ A Weighted Pair Graph Representation for Reconstructibility of Boolean Control Networks ⋮ New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems

Cites Work

• Supervisory control of \((\max,+)\) automata: a behavioral approach
• Supervisory Control of a Class of Discrete Event Processes
• Performance evaluation of (max,+) automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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