Results 21 to 30 of about 46,330 (328)
Resynchronized Uniformization and Definability Problems for Rational Relations [PDF]
Discrete 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
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
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
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
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
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
Minimization of visibly pushdown automata is NP-complete [PDF]
Logical Methods in Computer Science, 2020 We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such that ...
Olivier Gauwin +2 more
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