Results 11 to 20 of about 4,399 (316)
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
Automata and Formal Languages for Next Generation Sequencing Data
Electronic Proceedings in Theoretical Computer Science, 2017 Paola Bonizzoni, Gianluca Della Vedova
openaire +2 more sources
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
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
Crisp-determinization of weighted tree automata over strong bimonoids [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 We consider weighted tree automata (wta) over strong bimonoids and their initial algebra semantics and their run semantics. There are wta for which these semantics are different; however, for bottom-up deterministic wta and for wta over semirings, the ...
Zoltán Fülöp +2 more
doaj +1 more source
From Automata to Multiautomata via Theory of Hypercompositional Structures
Mathematics, 2021 In this paper, we study two important problems related to quasi-multiautomata: the complicated nature of verification of the GMAC condition for systems of quasi-multiautomata, and the fact that the nature of quasi-multiautomata has deviated from the ...
Štěpán Křehlík +2 more
doaj +1 more source
Locality and Centrality: The Variety ZG [PDF]
Logical Methods in Computer Science, 2023 We study the variety ZG of monoids where the elements that belong to a group are central, i.e., commute with all other elements. We show that ZG is local, that is, the semidirect product ZG * D of ZG by definite semigroups is equal to LZG, the variety of
Antoine Amarilli, Charles Paperman
doaj +1 more source
A model of actors and grey failures [PDF]
Logical Methods in Computer Science, 2023 Existing models for the analysis of concurrent processes tend to focus on fail-stop failures, where processes are either working or permanently stopped, and their state (working/stopped) is known.
Laura Bocchi +3 more
doaj +1 more source
Separation for dot-depth two [PDF]
Logical Methods in Computer Science, 2021 The dot-depth hierarchy of Brzozowski and Cohen classifies the star-free languages of finite words. By a theorem of McNaughton and Papert, these are also the first-order definable languages.
Thomas Place, Marc Zeitoun
doaj +1 more source