Results 11 to 20 of about 2,538 (309)
Automata Theory and Formal Languages [PDF]
, 2008 In this book we present some basic notions and results on Automata Theory, For- mal Language Theory, Computability Theory, and Parsing Theory. In particular, we consider the class of regular languages which are related to the class of finite automata, and the class of the context-free languages which are related to the class of pushdown automata.
Pettorossi, A, PETTOROSSI, ALBERTO
openaire +4 more sources
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
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