| 1 |
Between Deterministic and Nondeterministic Quantitative Automata (Invited Talk)
|
|
Boker, Udi. - : LIPIcs - Leibniz International Proceedings in Informatics. 30th EACSL Annual Conference on Computer Science Logic (CSL 2022), 2022
|
|
Abstract:
There is a challenging trade-off between deterministic and nondeterministic automata, where the former suit various applications better, however at the cost of being exponentially larger or even less expressive. This gave birth to many notions in between determinism and nondeterminism, aiming at enjoying, sometimes, the best of both worlds. Some of the notions are yes/no ones, for example initial nondeterminism (restricting nondeterminism to allowing several initial states), and some provide a measure of nondeterminism, for example the ambiguity level. We analyze the possible generalization of such notions from Boolean to quantitative automata, and suggest that it depends on the following key characteristics of the considered notion ? - whether it is syntactic or semantic, and if semantic, whether it is word-based or language-based. A syntactic notion, such as initial nondeterminism, applies as is to a quantitative automaton A, namely ?(A). A word-based semantic notion, such as unambiguity, applies as is to a Boolean automaton t-A that is derived from A by accompanying it with some threshold value t ? ?, namely ?(t-A). A language-based notion, such as history determinism, also applies as is to t-A, while in addition, it naturally generalizes into two different notions with respect to A itself, by either: i) taking the supremum of ?(t-A) over all thresholds t, denoted by Threshold-?(A); or ii) generalizing the basis of the notion from a language to a function, denoted simply by ?(A). While in general ?(A) ? Threshold-?(A) ? ?(t-A), we have for some notions ?(A) ? Threshold-?(A), and for some not. (For measure notions, ? stands for ? with respect to the nondeterminism level.) We classify numerous notions known in the Boolean setting according to their characterization above, generalize them to the quantitative setting and look into relations between them. The generalized notions open new research directions with respect to quantitative automata, and provide insights on the original notions with respect to Boolean automata.
|
|
Keyword:
Data processing Computer science; Determinism; Measure of Nondeterminism; Quantitative Automata
|
|
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15721/
https://doi.org/10.4230/LIPIcs.CSL.2022.1
https://nbn-resolving.org/urn:nbn:de:0030-drops-157218
|
|
BASE
|
|
Hide details
|
|
|
| 3 |
Latin Lemmatization & POS Tagging. Issues, Resources, Tools ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 4 |
Latin Lemmatization & POS Tagging. Issues, Resources, Tools ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 5 |
Mehrsprachigkeit und Translanguaging in Migrationsstudien: einige methodologische Überlegungen ; Multilingualism and Translanguaging in Migration Studies: Some Methodological Reflections
|
|
|
|
In: Forum Qualitative Sozialforschung / Forum: Qualitative Social Research; Bd. 23 Nr. 1 (2022) ; Forum Qualitative Sozialforschung / Forum: Qualitative Social Research; Vol. 23 No. 1 (2022) ; Forum Qualitative Sozialforschung / Forum: Qualitative Social Research; Vol. 23 Núm. 1 (2022) ; 1438-5627 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 6 |
A Corpus-Based Sentence Classifier for Entity–Relationship Modelling
|
|
|
|
In: Electronics; Volume 11; Issue 6; Pages: 889 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 7 |
Text Data Augmentation for the Korean Language
|
|
|
|
In: Applied Sciences; Volume 12; Issue 7; Pages: 3425 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 8 |
Connecting Text Classification with Image Classification: A New Preprocessing Method for Implicit Sentiment Text Classification
|
|
|
|
In: Sensors; Volume 22; Issue 5; Pages: 1899 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 9 |
FedQAS: Privacy-Aware Machine Reading Comprehension with Federated Learning
|
|
|
|
In: Applied Sciences; Volume 12; Issue 6; Pages: 3130 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 10 |
eHealth Engagement on Facebook during COVID-19: Simplistic Computational Data Analysis
|
|
|
|
In: International Journal of Environmental Research and Public Health; Volume 19; Issue 8; Pages: 4615 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 11 |
A Novel Method of Generating Geospatial Intelligence from Social Media Posts of Political Leaders
|
|
|
|
In: Information; Volume 13; Issue 3; Pages: 120 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 12 |
Multilingualism and Translanguaging in Migration Studies: Some Methodological Reflections
|
|
|
|
In: Forum Qualitative Sozialforschung / Forum: Qualitative Social Research ; 23 ; 1 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 13 |
Detecting weak and strong Islamophobic hate speech on social media
|
|
|
|
BASE
|
|
Show details
|
|
|
| 15 |
Maastricht University’s Multilingual Speech Translation System for IWSLT 2021
|
|
|
|
BASE
|
|
Show details
|
|
|
| 17 |
Toward Multilingual Neural Machine Translation with Universal Encoder and Decoder
|
|
|
|
BASE
|
|
Show details
|
|
|
| 18 |
The Karlsruhe Institute of Technology Systems for the News Translation Task in WMT 2017
|
|
|
|
BASE
|
|
Show details
|
|
|
| 19 |
Attention-Passing Models for Robust and Data-Efficient End-to-End Speech Translation
|
|
|
|
In: Transactions of the Association for Computational Linguistics, 7, 313–325 ; ISSN: 2307-387X (2022)
|
|
BASE
|
|
Show details
|
|
|
|
|
