Results 11 to 20 of about 3,411 (291)
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 prolog toolkit for formal languages and automata [PDF]
ACM SIGCSE Bulletin, 2005 This paper describes the first version of PFLAT (read "P flat"), a collection of Prolog predicates that aims to provide a pedagogical implementation of concepts and algorithms taught in Formal Languages and Automata Theory (FLAT) courses. By ``pedagogical implementation'' we mean on the one hand that students should be able to easily map the ...
Wermelinger, Michel, Dias, Artur Miguel
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
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
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
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
Watson-Crick conjugates of words and languages [PDF]
Discrete Mathematics & Theoretical Computer ScienceIn this work, we explore the concept of Watson-Crick conjugates, also known as $θ$-conjugates (where $θ$ is an antimorphic involution), of words and languages.
Kalpana Mahalingam, Anuran Maity
doaj +1 more source
Avoiding Shared Clocks in Networks of Timed Automata [PDF]
Logical Methods in Computer Science, 2013 Networks of timed automata (NTA) are widely used to model distributed real-time systems. Quite often in the literature, the automata are allowed to share clocks, i.e.
Sandie Balaguer, Thomas Chatain
doaj +1 more source