Goal-oriented reduction of automata networks

DOI10.1007/978-3-319-45177-0_16zbMATH Open1382.68137arXiv1608.05548OpenAlexW2252985226MaRDI QIDQ1706591FDOQ1706591

Authors: Loïc Paulevé 

Publication date: 22 March 2018

Abstract: We consider networks of finite-state machines having local transitions conditioned by the current state of other automata. In this paper, we depict a reduction procedure tailored for a given reachability property of the form ``from global state s there exists a sequence of transitions leading to a state where an automaton g is in a local state T'. By exploiting a causality analysis of the transitions within the individual automata, the proposed reduction removes local transitions while preserving all the minimal traces that satisfy the reachability property. The complexity of the procedure is polynomial in the total number of local states and transitions, and exponential in the number of local states within one automaton. Applied to automata networks modelling dynamics of biological systems, we observe that the reduction shrinks down significantly the reachable state space, enhancing the tractability of the model-checking of large networks.

Full work available at URL: https://arxiv.org/abs/1608.05548

Recommendations

• Sufficient conditions for reachability in automata networks with priorities
• Dynamically consistent reduction of logical regulatory graphs
• Reduction of Boolean network models
• Combining refinement of parametric models with goal-oriented reduction of dynamics
• scientific article; zbMATH DE number 4050939

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Cited In (9)

• Interval traces with mutex relation
• Goal-driven unfolding of Petri nets
• Consistent reduction in discrete-event systems
• Modeling delayed dynamics in biological regulatory networks from time series data
• Sufficient conditions for reachability in automata networks with priorities
• SAF: SAT-based attractor finder in asynchronous automata networks
• Combining refinement of parametric models with goal-oriented reduction of dynamics
• Algebraic structure of step traces and interval traces
• Classifying invariant structures of step traces

This page was built for publication: Goal-oriented reduction of automata networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1706591)