BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Tomáš Masopust

Tomáš Masopust contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Formal Languages and Automata Theorymath.OCSystems and Controlcs.CYeess.SY

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2020arXiv

On Verification of D-Detectability for Discrete Event Systems

Detectability has been introduced as a generalization of state-estimation properties of discrete event systems studied in the literature. It asks whether the current and subsequent states of a system can be determined based on observations. Since, in some applications, to exactly determine the current and subsequent states may be too strict, a relaxed notion of D-detectability has been introduced, distinguishing only certain pairs of states rather than all states. Four variants of D-detectability have been defined: strong (periodic) D-detectability and weak (periodic) D-detectability. Deciding weak (periodic) D-detectability is PSpace-complete, while deciding strong (periodic) detectability or strong D-detectability is polynomial (and we show that it is actually NL-complete). However, to the best of our knowledge, it is an open problem whether there exists a polynomial-time algorithm deciding strong periodic D-detectability. We solve this problem by showing that deciding strong periodic D-detectability is a PSpace-complete problem, and hence there is no polynomial-time algorithm unless PSpace = P. We further show that there is no polynomial-time algorithm deciding strong periodic D-detectability even for systems with a single observable event, unless P = NP. Finally, we propose a class of systems for which the problem is tractable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Note on Relative Observability in Coordination Control

Relative observability has been introduced and studied in the framework of partially observed discrete-event systems as a condition stronger than observability, but weaker than normality. However, unlike observability, relative observability is closed under language unions, which makes it interesting for practical applications. In this paper, we investigate this notion in the framework of coordination control. We prove that conditional normality is a stronger condition than conditional (strong) relative observability, hence conditional strong relative observability can be used in coordination control instead of conditional normality, and present a distributive procedure for the computation of a conditionally controllable and conditionally observable sublanguage of the specification that contains the supremal conditionally strong relative observable sublanguage.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Decentralized Supervisory Control with Communicating Supervisors Based on Top-Down Coordination Control

In this paper we present a new approach to decentralized supervisory control of large automata with communicating supervisors. We first generalize the recently developed top-down architecture of multilevel coordination control with a hierarchical structure of groups of subsystems, their respective coordinators and supervisors. Namely, in the case where the equivalent conditions for achieving a specification language fail to be satisfied, we propose sufficient conditions for a distributed computation of the supremal achievable sublanguage. We then apply the obtained constructive results of multilevel coordination control to decentralized supervisory control with communication, where local supervisors of subsystems within a group communicate with each other via the coordinator of the group. Our approach is illustrated by an example.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Maximally Permissive Coordination Supervisory Control -- Towards Necessary and Sufficient Conditions

In this paper, we further develop the coordination control framework for discrete-event systems with both complete and partial observation. A new weaker sufficient condition for the computation of the supremal conditionally controllable sublanguage is presented. This result is then used for the computation of the supremal conditionally controllable and conditionally normal sublanguage. The paper further generalizes the previous study by considering general, non-prefix-closed languages.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Upper and Lower Bounds on the Length of Alternating Towers

A tower between two regular languages is a sequence of strings such that all strings on odd positions belong to one of the languages, all strings on even positions belong to the other language, and each string can be embedded into the next string in the sequence. It is known that if there are towers of any length, then there also exists an infinite tower. We investigate upper and lower bounds on the length of finite towers between two regular languages with respect to the size of the automata representing the languages in the case there is no infinite tower. This problem is relevant to the separation problem of regular languages by piecewise testable languages.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Efficient Separability of Regular Languages by Subsequences and Suffixes

When can two regular word languages K and L be separated by a simple language? We investigate this question and consider separation by piecewise- and suffix-testable languages and variants thereof. We give characterizations of when two languages can be separated and present an overview of when these problems can be decided in polynomial time if K and L are given by nondeterministic automata.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the State Complexity of the Reverse of R- and J-trivial Regular Languages

The tight upper bound on the state complexity of the reverse of R-trivial and J-trivial regular languages of the state complexity n is 2^{n-1}. The witness is ternary for R-trivial regular languages and (n-1)-ary for J-trivial regular languages. In this paper, we prove that the bound can be met neither by a binary R-trivial regular language nor by a J-trivial regular language over an (n-2)-element alphabet. We provide a characterization of tight bounds for R-trivial regular languages depending on the state complexity of the language and the size of its alphabet. We show the tight bound for J-trivial regular languages over an (n-2)-element alphabet and a few tight bounds for binary J-trivial regular languages. The case of J-trivial regular languages over an (n-k)-element alphabet, for 2 <= k <= n-3, is open.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Note on Limited Pushdown Alphabets in Stateless Deterministic Pushdown Automata

Recently, an infinite hierarchy of languages accepted by stateless deterministic pushdown automata has been established based on the number of pushdown symbols. However, the witness language for the n-th level of the hierarchy is over an input alphabet with 2(n-1) elements. In this paper, we improve this result by showing that a binary alphabet is sufficient to establish this hierarchy. As a consequence of our construction, we solve the open problem formulated by Meduna et al. Then we extend these results to m-state realtime deterministic pushdown automata, for all m at least 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Note on Undecidability of Observation Consistency for Non-Regular Languages

One of the most interesting questions concerning hierarchical control of discrete-event systems with partial observations is a condition under which the language observability is preserved between the original and the abstracted plant. Recently, we have characterized two such sufficient conditions---observation consistency and local observation consistency. In this paper, we prove that the condition of observation consistency is undecidable for non-regular (linear, deterministic context-free) languages. The question whether the condition is decidable for regular languages is open.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Algorithms and Extensions of Coordination Control of Discrete-Event Systems

In this paper, we further develop the coordination control scheme for discrete-event systems based on the Ramadge-Wonham framework. The notions of conditional decomposability, conditional controllability, and conditional closedness are revised and simplified, supremal conditionally controllable sublanguages of general non-prefix-closed languages are discussed, and a procedure for the computation of a coordinator for nonblockingness is presented.

0 citations0 reviewsNo code linkedOpen access