Results 31 to 40 of about 914 (247)
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
Connector algebras for C/E and P/T nets' interactions [PDF]
Logical 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
Minimisation of Multiplicity Tree Automata [PDF]
Logical Methods in Computer Science, 2017 We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic.
Stefan Kiefer +2 more
doaj +1 more source
Regular tree languages in low levels of the Wadge Hierarchy [PDF]
Logical Methods in Computer Science, 2019 In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the ...
Mikołaj Bojańczyk +3 more
doaj +1 more source
Regular Languages in the Sliding Window Model [PDF]
TheoretiCSWe study the space complexity of the following problem: For a fixed regular language $L$, we receive a stream of symbols and want to test membership of a sliding window of size $n$ in $L$.
Moses Ganardi +4 more
doaj +1 more source
Computing the Width of Non-deterministic Automata [PDF]
Logical Methods in Computer Science, 2019 We introduce a measure called width, quantifying the amount of nondeterminism in automata. Width generalises the notion of good-for-games (GFG) automata, that correspond to NFAs of width 1, and where an accepting run can be built on-the-fly on any ...
Denis Kuperberg, Anirban Majumdar
doaj +1 more source
Completing the picture for the Skolem Problem on order-4 linear recurrence sequences [PDF]
TheoretiCSFor almost a century, the decidability of the Skolem Problem - that is, the problem of finding whether a given linear recurrence sequence (LRS) has a zero term - has remained open. A breakthrough in the 1980s established that the Skolem Problem is indeed
Piotr Bacik
doaj +1 more source
FO2(<,+1,~) on data trees, data tree automata and branching vector addition systems [PDF]
Logical Methods in Computer Science, 2016 A data tree is an unranked ordered tree where each node carries a label from a finite alphabet and a datum from some infinite domain. We consider the two variable first order logic FO2(
Florent Jacquemard +2 more
doaj +1 more source