Results 11 to 20 of about 45,230 (224)
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
A Characterization of Morphic Words with Polynomial Growth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 A morphic word is obtained by iterating a morphism to generate an infinite word, and then applying a coding. We characterize morphic words with polynomial growth in terms of a new type of infinite word called a $\textit{zigzag word}$.
Tim Smith
doaj +1 more source
Edit Distance for Pushdown Automata [PDF]
Logical Methods in Computer Science, 2017 The edit distance between two words $w_1, w_2$ is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform $w_1$ to $w_2$.
Krishnendu Chatterjee +3 more
doaj +1 more source
New tools for state complexity [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 A monster is an automaton in which every function from states to states is represented by at least one letter. A modifier is a set of functions allowing one to transform a set of automata into one automaton.
Pascal Caron +3 more
doaj +1 more source
On Separation by Locally Testable and Locally Threshold Testable Languages [PDF]
Logical Methods in Computer Science, 2014 A separator for two languages is a third language containing the first one and disjoint from the second one. We investigate the following decision problem: given two regular input languages, decide whether there exists a locally testable (resp. a locally
Thomas Place +2 more
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
Algebraic Language Theory for Eilenberg--Moore Algebras [PDF]
Logical Methods in Computer Science, 2021 We develop an algebraic language theory based on the notion of an Eilenberg--Moore algebra. In comparison to previous such frameworks the main contribution is the support for algebras with infinitely many sorts and the connection to logic in form of so ...
Achim Blumensath
doaj +1 more source
Separation Property for wB- and wS-regular Languages [PDF]
Logical Methods in Computer Science, 2014 In this paper we show that {\omega}B- and {\omega}S-regular languages satisfy the following separation-type theorem If L1,L2 are disjoint languages of {\omega}-words both recognised by {\omega}B- (resp.
Michał Skrzypczak
doaj +1 more source