Results 31 to 40 of about 43,821 (313)

From Automata to Multiautomata via Theory of Hypercompositional Structures

open access: yesMathematics, 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

Resynchronized Uniformization and Definability Problems for Rational Relations [PDF]

open access: yesDiscrete Mathematics & Theoretical Computer Science, 2023
Regular synchronization languages can be used to define rational relations of finite words, and to characterize subclasses of rational relations, like automatic or recognizable relations.
Christof Löding, Sarah Winter
doaj   +1 more source

On Separation by Locally Testable and Locally Threshold Testable Languages [PDF]

open access: yesLogical 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

Transfinite Lyndon words [PDF]

open access: yesLogical Methods in Computer Science, 2020
In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the ...
Olivier Carton, Luc Boasson
doaj   +1 more source

Separation Property for wB- and wS-regular Languages [PDF]

open access: yesLogical 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

Avoiding Shared Clocks in Networks of Timed Automata [PDF]

open access: yesLogical 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

Equivalence checking for weak bi-Kleene algebra [PDF]

open access: yesLogical 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

Connector algebras for C/E and P/T nets' interactions [PDF]

open access: yesLogical Methods in Computer Science, 2013
A quite flourishing research thread in the recent literature on component-based systems is concerned with the algebraic properties of different classes of connectors.
Roberto Bruni   +3 more
doaj   +1 more source

The Power-Set Construction for Tree Algebras [PDF]

open access: yesLogical 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]

open access: yesLogical 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

Home - About - Disclaimer - Privacy