Titlebook: Developments in Language Theory; 23rd International C Piotrek Hofman,Michał Skrzypczak Conference proceedings 2019 Springer Nature Switzerl

Mri485

Input-Driven Pushdown Automata for Edit Distance Neighborhoodtates, which improves the known upper bound. We have obtained also a lower bound, namely, at least . states are required. If the measure of edit distance includes also the operation of rewriting one symbol with another, the edit distance .-neighborhood can be recognized with . pushdown symbols and . states.

贞洁

Eventually Safe Languagesanguages. We introduce a class of properties called “eventually safe” together with a specification language . for this class. We finally give an algorithm to produce a Good-for-Games automaton from any . formula, thereby allowing synthesis for eventually safe properties.

DUCE

ADORN

Sachin A. Gupte,Michael S. Wolin in the deterministic setting it allows for exponential succinctness compared to the classic types, boolean operations on it only involve a quadratic size blowup, and its nonemptiness, universality, and containment checks are in PTIME.

hieroglyphic

Inherent Size Blowup in ,-Automata in the deterministic setting it allows for exponential succinctness compared to the classic types, boolean operations on it only involve a quadratic size blowup, and its nonemptiness, universality, and containment checks are in PTIME.

饥荒

不满分子

凹处

Characterizing the Valuedness of Two-Way Finite Transducersalued or not. As crossing sequences in two-way automata often play similar roles as states in their one-way counterparts, we derive in this paper analogous criteria in the setting of crossing sequences to characterize the infinite-valuedness of two-way finite transducers.

沉思的鱼

Fracture

Coinductive Algorithms for Büchi Automatan generates large and highly non-deterministic automata, we show how to exploit their specific structure and apply state-of-the art techniques based on coinduction to reduce the state-space that has to be explored. Doing so, we obtain algorithms which do not require full determinization or complementation.