Automata Theory and Formal Languages

Complexity of universality (inclusion, equivalence) of (restricted) partially ordered NFAs

  1. Krötzsch, M., Masopust, T., Thomazo, M., On the Complexity of Universality for Partially Ordered NFAs, MFCS 2016
Files: MFCS 2016, Full version, Summary
Presentations: Overview

(k-)piecewise-testability and nondeterministic automata -- characterization and complexity

  1. Masopust, T., Piecewise Testable Languages and Nondeterministic Automata, MFCS 2016
Files: MFCS 2016, TCS, SOFSEM 2018

Separability of regular languages by piecewise testable languages

  1. Czerwiński, W., Martens, W., Masopust, T., Efficient Separability of Regular Languages by Subsequences and Suffixes, ICALP 2013
  2. Masopust, T., Separability by Piecewise Testable Languages is PTime-Complete, Theoretical Computer Science 711, 109-114, 2018
Files: ICALP 2013, complexity

New normal forms for random context and matrix grammars

  1. Dassow, J., Masopust, T., On restricted context-free grammars, Journal of Computer and System Sciences 78, 293-304, 2012
Files: JCSS

Discrete-Event Systems

Hierarchical and modular supervisory control

  1. Komenda, J., Masopust, T., Hierarchical Supervisory Control under Partial Observation: Normality, IEEE Transactions on Automatic Control 68(12), 7286-7298, 2023
  2. Komenda, J., Masopust, T., Supervisory Control of Modular Discrete-Event Systems under Partial Observation: Normality, IEEE Transactions on Automatic Control, scheduled for Volume 69 (2024), Issue 6 (June)
Files: TAC 2023, TAC 2024

Coordination control and its applications

  1. Komenda, J., Masopust, T., Van Schuppen, J.H., On a Distributed Computation of Supervisors in Modular Supervisory Control, ICCSE 2015
  2. Komenda, J., Masopust, T., van Schuppen J.H., Coordination Control of Discrete-Event Systems Revisited, Discrete Event Dynamic Systems, 25, 65-94, 2015
  3. Komenda, J., Masopust, T., van Schuppen, J.H., Supervisory Control Synthesis of Discrete-Event Systems using a Coordination Scheme, Automatica 48, 247-254, 2012
Files: ICCSE 2015, JDEDS, Automatica

Decentralized supervisory control with communication

  1. Komenda, J., Masopust, T., Computation of Controllable and Coobservable Sublanguages in Decentralized Supervisory Control via Communication, Discrete Event Dynamic Systems 27(4), 585-608, 2017.
Files: JDEDS

Controllability of deterministic context-free systems

  1. Masopust, T., A note on controllability of deterministic context-free systems, Automatica 48, 1934-1937, 2012
Files: Automatica

Opacity, Diagnosability, Detectability, Nonblockingness, etc.

Complexity

  1. Masopust, T., Complexity of Verifying Nonblockingness in Modular Supervisory Control, IEEE Transactions on Automatic Control, 63(2), 602-607, 2018
  2. Masopust, T., Complexity of Infimal Observable Superlanguages, IEEE Transactions on Automatic Control, 63(1), 249-254, 2018
  3. Masopust, T., Complexity of Deciding Detectability in Discrete Event Systems, Automatica 93, 257-261, 2018
  4. Masopust, T., Yin, X., Complexity of Detectability, Opacity and A-Diagnosability for Modular Discrete Event Systems, Automatica 101, 290-295, 2019
  5. Balun, J., Masopust, T., Comparing the Notions of Opacity for Discrete-Event Systems, Discrete Event Dynamic Systems 31, 553-582, 2021
  6. Balun, J., Masopust, T., Verifying Weak and Strong k-Step Opacity in Discrete-Event Systems, Automatica 155, 111153, 2023
Files: arXiv 1, arXiv 2, arxiv 3, arxiv 4, JDEDS 2021, Automatica 2023

Fine-grained complexity

  1. Balun, J., Masopust, T., Osička, P., Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification, International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), LIPIcs 272, 16:1--16:15, 2023.
Files: MFCS 2023

Liveness in Transportation Systems

Guidepath-based transport systems

  1. Reveliotis, S., Masopust, T., Ibrahim, M., Polynomial-Time Optimal Liveness Enforcement for Guidepath-based Transport Systems, Nonlinear Analysis: Hybrid Systems 41, 101058, 2021
    2. Files: NAHS