Results 21 to 30 of about 48,609 (342)
Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languages [PDF]
IEEE International Conference on Formal Engineering Methods, 2022 Recurrent Neural Networks (RNNs) have achieved tremendous success in sequential data processing. However, it is quite challenging to interpret and verify RNNs' behaviors directly.
Zeming Wei, Xiyue Zhang, Meng Sun
semanticscholar +1 more source
Minimization of visibly pushdown automata is NP-complete [PDF]
Logical Methods in Computer Science, 2020 We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such that ...
Olivier Gauwin +2 more
doaj +1 more source
A Course in Formal Languages, Automata and Groups
Choice Reviews Online, 2009 I. Chiswell
semanticscholar +3 more sources
Most Complex Regular Ideal Languages [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 A right ideal (left ideal, two-sided ideal) is a non-empty language $L$ over an alphabet $\Sigma$ such that $L=L\Sigma^*$ ($L=\Sigma^*L$, $L=\Sigma^*L\Sigma^*$). Let $k=3$ for right ideals, 4 for left ideals and 5 for two-sided ideals. We show that there
Janusz Brzozowski +2 more
doaj +1 more source
A Theory of Formal Choreographic Languages [PDF]
Log. Methods Comput. Sci., 2022 We introduce a meta-model based on formal languages, dubbed formal choreographic languages, to study message-passing systems. Our framework allows us to generalise standard constructions from the literature and to compare them. In particular, we consider
F. Barbanera, Ivan Lanese, E. Tuosto
semanticscholar +1 more source
Decidability of multiset, set and numerically decipherable directed figure codes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 Codes with various kinds of decipherability, weaker than the usual unique decipherability, have been studied since multiset decipherability was introduced in mid-1980s.
Włodzimierz Moczurad
doaj +1 more source
Equivalence checking for weak bi-Kleene algebra [PDF]
Logical Methods in Computer Science, 2021 Pomset automata are an operational model of weak bi-Kleene algebra, which describes programs that can fork an execution into parallel threads, upon completion of which execution can join to resume as a single thread.
Tobias Kappé +4 more
doaj +1 more source
The Power-Set Construction for Tree Algebras [PDF]
Logical Methods in Computer Science, 2023 We study power-set operations on classes of trees and tree algebras. Our main result consists of a distributive law between the tree monad and the upwards-closed power-set monad, in the case where all trees are assumed to be linear.
Achim Blumensath
doaj +1 more source
Token Games and History-Deterministic Quantitative-Automata [PDF]
Logical Methods in Computer Science, 2023 A nondeterministic automaton is history-deterministic if its nondeterminism can be resolved by only considering the prefix of the word read so far. Due to their good compositional properties, history-deterministic automata are useful in solving games and
Udi Boker, Karoliina Lehtinen
doaj +1 more source