BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Tomáš Masopust

Tomáš Masopust appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata Theorymath.OCSystems and Controlcs.CYeess.SY

Catalog footprint

What is connected

17works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

17 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
preprint2016arXiv

On a Distributed Computation of Supervisors in Modular Supervisory Control

In this paper, we discuss a supervisory control problem of modular discrete-event systems that allows for a distributed computation of supervisors. We provide a characterization and an algorithm to compute the supervisors. If the specification does not satisfy the properties, we make use of a relaxation of coordination control to compute a sublanguage of the specification for which the supervisors can be computed in a distributed way.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Piecewise Testable Languages and Nondeterministic Automata

A regular language is $k$-piecewise testable if it is a finite boolean combination of languages of the form $Σ^* a_1 Σ^* \cdots Σ^* a_n Σ^*$, where $a_i\inΣ$ and $0\le n \le k$. Given a DFA $A$ and $k\ge 0$, it is an NL-complete problem to decide whether the language $L(A)$ is piecewise testable and, for $k\ge 4$, it is coNP-complete to decide whether the language $L(A)$ is $k$-piecewise testable. It is known that the depth of the minimal DFA serves as an upper bound on $k$. Namely, if $L(A)$ is piecewise testable, then it is $k$-piecewise testable for $k$ equal to the depth of $A$. In this paper, we show that some form of nondeterminism does not violate this upper bound result. Specifically, we define a class of NFAs, called ptNFAs, that recognize piecewise testable languages and show that the depth of a ptNFA provides an (up to exponentially better) upper bound on $k$ than the minimal DFA. We provide an application of our result, discuss the relationship between $k$-piecewise testability and the depth of NFAs, and study the complexity of $k$-piecewise testability for ptNFAs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Relaxed Framework for Coordination Control of Discrete-Event Systems

In this paper, we simplify the coordination control approach by removing the supervisor for the coordinator from the closed-loop system and relax the restrictions placed on a coordinator. This relaxation results in the simplification of the whole coordination control framework, including the notions of conditional controllability, conditional observability, and conditional normality. Compared to our previous work, the role of the supervisor on a coordinator alphabet is postponed until the final stage of the coordination control synthesis. This completes and clarifies our previous results, while all the fundamental theorems remain valid in the relaxed framework. Unlike previous approaches we can always compute a conditionally controllable sublanguage without any restricting conditions we have used before.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Alternating Towers and Piecewise Testable Separators

Two languages are separable by a piecewise testable language if and only if there exists no infinite tower between them. An infinite tower is an infinite sequence of strings alternating between the two languages such that every string is a subsequence (scattered substring) of all the strings that follow. For regular languages represented by nondeterministic finite automata, the existence of an infinite tower is decidable in polynomial time. In this paper, we investigate the complexity of a particular method to compute a piecewise testable separator. We show that it is closely related to the height of maximal finite towers, and provide the upper and lower bounds with respect to the size of the given nondeterministic automata. Specifically, we show that the upper bound is polynomial with respect to the number of states with the cardinality of the alphabet in the exponent. Concerning the lower bound, we show that towers of exponential height with respect to the cardinality of the alphabet exist. Since these towers mostly turn out to be sequences of prefixes, we also provide a comparison with towers of prefixes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Combined Top-down and Bottom-up Approach to Multilevel Supervisory Control

Recently, we have proposed two complementary approaches, top-down and bottom-up, to multilevel supervisory control of discrete-event systems. In this paper, we compare and combine these approaches. The combined approach has strong features of both approaches, namely, a lower complexity of the top-down approach with the generality of the bottom-up approach. We show that, for prefix-closed languages, a posteriori supervisors computed in the bottom-up manner do not alter maximal permissiveness within the three-level coordination control architecture, that is, the supremal three-level conditionally-controllable and conditionally-normal language can always be computed in a distributed way using multilevel coordination. Moreover, a general polynomial-time procedure for non-prefix closed case is proposed based on coordinators for nonblockingness and a posteriori supervisors.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On $k$-piecewise testability (preliminary report)

For a non-negative integer $k$, a language is $k$-piecewise test\-able ($k$-PT) if it is a finite boolean combination of languages of the form $Σ^* a_1 Σ^* \cdots Σ^* a_n Σ^*$ for $a_i\inΣ$ and $0\le n \le k$. We study the following problem: Given a DFA recognizing a piecewise testable language, decide whether the language is $k$-PT. We provide a complexity bound and a detailed analysis for small $k$'s. The result can be used to find the minimal $k$ for which the language is $k$-PT. We show that the upper bound on $k$ given by the depth of the minimal DFA can be exponentially bigger than the minimal possible $k$, and provide a tight upper bound on the depth of the minimal DFA recognizing a $k$-PT language.

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 Conditional Decomposability

The requirement of a language to be conditionally decomposable is imposed on a specification language in the coordination supervisory control framework of discrete-event systems. In this paper, we present a polynomial-time algorithm for the verification whether a language is conditionally decomposable with respect to given alphabets. Moreover, we also present a polynomial-time algorithm to extend the common alphabet so that the language becomes conditionally decomposable. A relationship of conditional decomposability to nonblockingness of modular discrete-event systems is also discussed in this paper in the general settings. It is shown that conditional decomposability is a weaker condition than nonblockingness.

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