Results 11 to 20 of about 242 (42)
Descriptional Complexity of Finite Automata -- Selected Highlights
, 2023 The state complexity, respectively, nondeterministic state complexity of a regular language $L$ is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for $L$.
Salomaa, Arto +2 more
core
The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications [PDF]
, 2017 The principle goal of computational mechanics is to define pattern and structure so that the organization of complex systems can be detected and quantified.
Crutchfield, James P.
core +1 more source
Kunz languages for numerical semigroups are context sensitive
, 2023 There is a one-to-one and onto correspondence between the class of numerical semigroups of depth $n$, where $n$ is an integer, and a certain language over the alphabet $\{1,\ldots,n\}$ which call Kunz language of depth $n$.
Cubertorer, Usó i, Delgado, Manuel
core
Real-time Regular Expression Matching
, 2023 This paper is devoted to finite state automata, regular expression matching, pattern recognition, and the exponential blow-up problem, which is the growing complexity of automata exponentially depending on regular expression length. This paper presents a
Bernadotte, Alexandra
core
An approach to computing downward closures
, 2015 The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular.
A Ehrenfeucht +17 more
core +1 more source
Weighted languages recognizable by weighted tree automata [PDF]
, 2018 Yields of recognizable weighted tree languages, yields of local weighted tree languages, and weighted context-free languages are related. It is shown that the following five classes of weighted languages are the same: (i) the class of weighted languages ...
Fülöp Zoltán, Gazdag Zsolt
core
Colored operads, series on colored operads, and combinatorial generating systems [PDF]
, 2019 We introduce bud generating systems, which are used for combinatorial generation. They specify sets of various kinds of combinatorial objects, called languages.
Giraudo, Samuele
core +1 more source
String Diagrammatic Trace Theory
, 2023 We extend the theory of formal languages in monoidal categories to the multi-sorted, symmetric case, and show how this theory permits a graphical treatment of topics in concurrency.
Earnshaw, Matthew, Sobociński, Paweł
core
Classical and quantum Merlin-Arthur automata
, 2022 We introduce Merlin-Arthur (MA) automata as Merlin provides a single certificate and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, MA ...
Yakaryılmaz, Abuzer
core
Alternating weak automata from universal trees [PDF]
, 2019 An improved translation from alternating parity automata on infinite words to alternating weak automata is given. The blow-up of the number of states is related to the size of the smallest universal ordered trees and hence it is quasi-polynomial, and it ...
Daviaud, Laure +2 more
core +1 more source