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

Anca Muscholl

Anca Muscholl appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer ScienceFormal Languages and Automata TheorySystems and ControlDatabasesOther Computer Science

Catalog footprint

What is connected

13works
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

13 published item(s)

preprint2022arXiv

Active Learning for Sound Negotiations

We present two active learning algorithms for sound deterministic negotiations. Sound deterministic negotiations are models of distributed systems, a kind of Petri nets or Zielonka automata with additional structure. We show that this additional structure allows to minimize such negotiations. The two active learning algorithms differ in the type of membership queries they use. Both have similar complexity to Angluin's L* algorithm, in particular, the number of queries is polynomial in the size of the negotiation, and not in the number of configurations.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

One-way resynchronizability of word transducers

The origin semantics for transducers was proposed in 2014, and led to various characterizations and decidability results that are in contrast with the classical semantics. In this paper we add a further decidability result for characterizing transducers that are close to one-way transducers in the origin semantics. We show that it is decidable whether a non-deterministic two-way word transducer can be resynchronized by a bounded, regular resynchronizer into an origin-equivalent one-way transducer. The result is in contrast with the usual semantics, where it is undecidable to know if a non-deterministic two-way transducer is equivalent to some one-way transducer.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On parametrized verification of asynchronous, shared-memory pushdown systems

We consider the model of parametrized asynchronous shared-memory pushdown systems, as introduced in [Hague'11]. In a series of recent papers it has been shown that reachability in this model is PSPACE-complete [Esparza, Ganty, Majumdar'13] and that liveness is decidable in NEXPTIME [Durand-Gasselin, Esparza, Ganty, Majumdar'15]. We show here that the liveness problem is PSPACE-complete. We also introduce the universal reachability problem. We show that it is decidable, and coNEXPTIME-complete. Finally, using these results, we prove that the verifying regular properties of traces of executions, satisfying some stuttering condition, is also decidable in NEXPTIME for this model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Reachability for dynamic parametric processes

In a dynamic parametric process every subprocess may spawn arbitrarily many, identical child processes, that may communicate either over global variables, or over local variables that are shared with their parent. We show that reachability for dynamic parametric processes is decidable under mild assumptions. These assumptions are e.g. met if individual processes are realized by pushdown systems, or even higher-order pushdown systems. We also provide algorithms for subclasses of pushdown dynamic parametric processes, with complexity ranging between NP and DEXPTIME.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Note on Monitors and Büchi automata

When a property needs to be checked against an unknown or very complex system, classical exploration techniques like model-checking are not applicable anymore. Sometimes a~monitor can be used, that checks a given property on the underlying system at runtime. A monitor for a property $L$ is a deterministic finite automaton $M_L$ that after each finite execution tells whether (1) every possible extension of the execution is in $L$, or (2) every possible extension is in the complement of $L$, or neither (1) nor (2) holds. Moreover, $L$ being monitorable means that it is always possible that in some future the monitor reaches (1) or (2). Classical examples for monitorable properties are safety and cosafety properties. On the other hand, deterministic liveness properties like "infinitely many $a$'s" are not monitorable. We discuss various monitor constructions with a focus on deterministic omega-regular languages. We locate a proper subclass of of deterministic omega-regular languages but also strictly large than the subclass of languages which are deterministic and codeterministic, and for this subclass there exists a canonical monitor which also accepts the language itself. We also address the problem to decide monitorability in comparison with deciding liveness. The state of the art is as follows. Given a Büchi automaton, it is PSPACE-complete to decide liveness or monitorability. Given an LTL formula, deciding liveness becomes EXPSPACE-complete, but the complexity to decide monitorability remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Automated Synthesis of Distributed Controllers

Synthesis is a particularly challenging problem for concurrent programs. At the same time it is a very promising approach, since concurrent programs are difficult to get right, or to analyze with traditional verification techniques. This paper gives an introduction to distributed synthesis in the setting of Mazurkiewicz traces, and its applications to decentralized runtime monitoring. 1 Context Modern computing systems are increasingly distributed and heterogeneous. Software needs to be able to exploit these advances, providing means for applications to be more performant. Traditional concurrent programming paradigms, as in Java, are based on threads, shared-memory, and locking mechanisms that guard access to common data. More recent paradigms like the reactive programming model of Erlang [4] and Scala [35,36] replace shared memory by asynchronous message passing, where sending a message is non-blocking. In all these concurrent frameworks, writing reliable software is a serious challenge. Programmers tend to think about code mostly in a sequential way, and it is hard to grasp all possible schedulings of events in a concurrent execution. For similar reasons, verification and analysis of concurrent programs is a difficult task. Testing, which is still the main method for error detection in software, has low coverage for concurrent programs. The reason is that bugs in such programs are difficult to reproduce: they may happen under very specific thread schedules and the likelihood of taking such corner-case schedules is very low. Automated verification, such as model-checking and other traditional exploration techniques, can handle very limited instances of concurrent programs, mostly because of the very large number of possible states and of possible interleavings of executions. Formal analysis of programs requires as a prerequisite a clean mathematical model for programs. Verification of sequential programs starts usually with an abstraction step -- reducing the value domains of variables to finite domains, viewing conditional branching as non-determinism, etc. Another major simplification consists in disallowing recursion. This leads to a very robust computational model, namely finite-state automata and regular languages. Regular languages of words (and trees) are particularly well understood notions. The deep connections between logic and automata revealed by the foundational work of Büchi, Rabin, and others, are the main ingredients in automata-based verification .

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Distributed synthesis for acyclic architectures

The distributed synthesis problem is about constructing cor- rect distributed systems, i.e., systems that satisfy a given specification. We consider a slightly more general problem of distributed control, where the goal is to restrict the behavior of a given distributed system in order to satisfy the specification. Our systems are finite state machines that communicate via rendez-vous (Zielonka automata). We show decidability of the synthesis problem for all omega-regular local specifications, under the restriction that the communication graph of the system is acyclic. This result extends a previous decidability result for a restricted form of local reachability specifications.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Asynchronous Games over Tree Architectures

We consider the task of controlling in a distributed way a Zielonka asynchronous automaton. Every process of a controller has access to its causal past to determine the next set of actions it proposes to play. An action can be played only if every process controlling this action proposes to play it. We consider reachability objectives: every process should reach its set of final states. We show that this control problem is decidable for tree architectures, where every process can communicate with its parent, its children, and with the environment. The complexity of our algorithm is l-fold exponential with l being the height of the tree representing the architecture. We show that this is unavoidable by showing that even for three processes the problem is EXPTIME-complete, and that it is non-elementary in general.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On distributed monitoring of asynchronous systems

Distributed systems are notoriously difficult to understand and analyze in order to assert their correction w.r.t. given properties. They often exhibit a huge number of different behaviors, as soon as the active entities (peers, agents, processes, etc) behave in an asynchronous manner. Already the modelization of such systems is a non-trivial task, let alone their formal verification. The purpose of this paper is to discuss the problem of distributed monitoring on a simple model of finite-state distributed automata based on shared actions, called asynchronous automata. Monitoring is a question related to runtime verification: assume that we have to check a property $L$ against an unknown or very complex system $A$, so that classical static analysis is not possible. Therefore instead of model-checking a monitor is used, that checks the property on the underlying system at runtime. We are interested here in monitoring distributed systems modeled as asynchronous automata. It is natural to require that monitors should be of the same kind as the underlying system, so we consider here distributed monitoring. A distributed monitor does not have a global view of the system, therefore we propose the notion of locally monitorable trace language. Our main result shows that if the distributed alphabet of actions is connected and if $L$ is a set of infinite traces such that both $L$ and its complement $L^c$ are countable unions of locally safety languages, then $L$ is locally monitorable. We also show that over infinite traces, recognizable countable unions of locally safety languages are precisely the complements of deterministic languages.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Injective Embeddings of Tree Patterns

We study three different kinds of embeddings of tree patterns: weakly-injective, ancestor-preserving, and lca-preserving. While each of them is often referred to as injective embedding, they form a proper hierarchy and their computational properties vary (from P to NP-complete). We present a thorough study of the complexity of the model checking problem i.e., is there an embedding of a given tree pattern in a given tree, and we investigate the impact of various restrictions imposed on the tree pattern: bound on the degree of a node, bound on the height, and type of allowed labels and edges.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reachability Analysis of Communicating Pushdown Systems

The reachability analysis of recursive programs that communicate asynchronously over reliable FIFO channels calls for restrictions to ensure decidability. Our first result characterizes communication topologies with a decidable reachability problem restricted to eager runs (i.e., runs where messages are either received immediately after being sent, or never received). The problem is EXPTIME-complete in the decidable case. The second result is a doubly exponential time algorithm for bounded context analysis in this setting, together with a matching lower bound. Both results extend and improve previous work from La Torre et al.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Verifying Recursive Active Documents with Positive Data Tree Rewriting

This paper proposes a data tree-rewriting framework for modeling evolving documents. The framework is close to Guarded Active XML, a platform used for handling XML repositories evolving through web services. We focus on automatic verification of properties of evolving documents that can contain data from an infinite domain. We establish the boundaries of decidability, and show that verification of a {\em positive} fragment that can handle recursive service calls is decidable. We also consider bounded model-checking in our data tree-rewriting framework and show that it is $\nexptime$-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

A lower bound on web services composition

A web service is modeled here as a finite state machine. A composition problem for web services is to decide if a given web service can be constructed from a given set of web services; where the construction is understood as a simulation of the specification by a fully asynchronous product of the given services. We show an EXPTIME-lower bound for this problem, thus matching the known upper bound. Our result also applies to richer models of web services, such as the Roman model.

0 citations0 reviewsNo code linkedOpen access