Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Minimisation and Language Inclusion for Separating B\"uchi and Parity Automata
View through CrossRef
We provide simple proofs of the NC results for the universality, language inclusion, and equivalence problems of unambiguous finite automata, based on recent advances in model checking.We extend all complexity results to separating parity automata and to a restricted class of separating generalised B\"uchi automata, and introduce natural distance metrics for regular and $\omega$-regular languages that can be computed in NC for these classes of automata.As a side result, we show that we can also check universality of run-unambiguous automata---automata that have at most one run for every infinite word---in NC. Lastly, we also show that the minimisation problem is NP-complete for separating automata and NP-hard for unambiguous automata and run-unambiguous automata.
Title: Minimisation and Language Inclusion for Separating B\"uchi and Parity Automata
Description:
We provide simple proofs of the NC results for the universality, language inclusion, and equivalence problems of unambiguous finite automata, based on recent advances in model checking.
We extend all complexity results to separating parity automata and to a restricted class of separating generalised B\"uchi automata, and introduce natural distance metrics for regular and $\omega$-regular languages that can be computed in NC for these classes of automata.
As a side result, we show that we can also check universality of run-unambiguous automata---automata that have at most one run for every infinite word---in NC.
Lastly, we also show that the minimisation problem is NP-complete for separating automata and NP-hard for unambiguous automata and run-unambiguous automata.
Related Results
Hubungan Perilaku Pola Makan dengan Kejadian Anak Obesitas
Hubungan Perilaku Pola Makan dengan Kejadian Anak Obesitas
<p><em><span style="font-size: 11.0pt; font-family: 'Times New Roman',serif; mso-fareast-font-family: 'Times New Roman'; mso-ansi-language: EN-US; mso-fareast-langua...
Učinak poučavanja razrednomu jeziku u izobrazbi nastavnika njemačkoga
Učinak poučavanja razrednomu jeziku u izobrazbi nastavnika njemačkoga
The actual use of classroom language is principally limited to the classroom environment. As far as foreign language learning is concerned, the classroom often turns out to be the ...
Konsep Uchi-Soto Dalam Penerjemahan Yari-Morai
Konsep Uchi-Soto Dalam Penerjemahan Yari-Morai
This study aims to describe the understanding of Japanese language students about the ‘uchi-soto’ concept which is the standard for Japanese people when using the ‘yari-mor...
Simulations for Event-Clock Automata
Simulations for Event-Clock Automata
Event-clock automata (ECA) are a well-known semantic subclass of timed
automata (TA) which enjoy admirable theoretical properties, e.g.,
determinizability, and are practically usef...
A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
AbstractIn this paper, we consider a model of generalized timed automata (GTA) with two kinds of clocks, history and future, that can express many timed features succinctly, includ...
Increased life expectancy of heart failure patients in a rural center by a multidisciplinary program
Increased life expectancy of heart failure patients in a rural center by a multidisciplinary program
Abstract
Funding Acknowledgements
Type of funding sources: None.
INTRODUCTION Patients with heart failure (HF)...
Permutation Groups in Automata Diagrams
Permutation Groups in Automata Diagrams
Automata act as classical models for recognition devices. From the previous researches, the classical models of automata have been used to scan strings and to determine the types o...
DFA Resolutions of B¨uchi Automata:Pro-Objects, Closure Properties, and Model Checking
DFA Resolutions of B¨uchi Automata:Pro-Objects, Closure Properties, and Model Checking
We develop a categorical framework in which B¨uchi automata are representedas pro-objects (formal cofiltered limits) in the category AutΣ of deterministic fi-nite automata over an ...