Results 31 to 40 of about 242 (42)
An Elementary Proof of the FMP for Kleene Algebra
, 2023 Kleene Algebra (KA) is a useful tool for proving that two programs are equivalent by reasoning equationally. Because it abstracts from the meaning of primitive programs, KA's equational theory is decidable, so it integrates well with interactive theorem ...
Kappé, Tobias
core
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems
, 2022 We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The definition of an ADS is based on the language of protocols of work with the ADS.
Rubtsov, Alexander, Vyalyi, Mikhail
core
Learning Formal Specifications from Membership and Preference Queries
, 2023 Active learning is a well-studied approach to learning formal specifications, such as automata. In this work, we extend active specification learning by proposing a novel framework that strategically requests a combination of membership labels and pair ...
Junges, Sebastian +3 more
core
Separating Automatic Relations
, 2023 We study the separability problem for automatic relations (i.e., relations on finite words definable by synchronous automata) in terms of recognizable relations (i.e., finite unions of products of regular languages).
Barceló, Pablo +2 more
core
On Minimization and Learning of Deterministic $\omega$-Automata in the Presence of Don't Care Words
, 2023 We study minimization problems for deterministic $\omega$-automata in the presence of don't care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don't care words.
Löding, Christof, Stachon, Max Philip
core
On the Representation of Block Languages
In this paper we consider block languages, namely sets of words having the same length, and we propose a new representation for these languages. In particular, given an alphabet of size $k$ and a length $\ell$, these languages can be represented by ...
Duarte, Guilherme +3 more
core
The generating power of weighted tree automata with initial algebra semantics
We consider the images of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings). These images are subsets of the carrier set of the underlying strong bimonoid. We consider locally finite, weakly locally
Droste, Manfred +3 more
core
Addition in Dumont-Thomas Numeration Systems in Theory and Practice
Given a fixpoint of a substitution, the associated Dumont-Thomas numeration system provides a convenient immediate way to describe the fixpoint as an automatic sequence.
Carton, Olivier +3 more
core
Logic and Languages of Higher-Dimensional Automata
In this paper we study finite higher-dimensional automata (HDAs) from the logical point of view.
Amrane, Amazigh +3 more
core
Window Expressions for Stream Data Processing
Traditional ways of storing and querying data do not work well in scenarios where data is being generated continuously and quick decisions need to be taken. For example, in hospital intensive care units, signals from multiple devices need to be monitored
Hitarth, S., Praveen, M.
core