Descriptional Complexity of Formal Systems, 1st ed. 2021 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings Theoretical Computer Science and General Issues Series
Coordonnateurs : Han Yo-Sub, Ko Sang-Ki
The 16 full papers presented in this volume were carefully reviewed and selected from 21 submissions. The conference focus to all aspects of descriptional complexity-the costs of description of objects in various computational models such as Turing machines, pushdown automata, finite automata or grammars.
Complexity issues for the iterated h-preorders.- On the Uniform Distribution of Regular Expressions.- Deterministic one-way simulation of two-way deterministic finite automata over small alphabets.- Sync-Maximal Permutation Groups Equal Primitive Permutation Groups.- Commutative Regular Languages with Product-Form Minimal Automata.- State Complexity Bounds for Upward and Downward Closures on Commutative Languages and Commutative Group and Commutative Aperiodic Languages.- More on the Descriptional Complexity of Compositions of Finite Automata.- Width Measures of Alternating Finite Automata.- Partial Derivative Automaton by Compressing Regular Expressions.- State Complexity of Partial Word Finite Automata.- State complexity of union and intersection on graph-walking automata.- Gray cycles of maximum length related to $k$-character substitutions.- Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems.- Disambiguation of Weighted Tree Automata.- Image-Binary Automata.- Improved constructions for succinct affine automata.
Date de parution : 12-2021
Ouvrage de 201 p.
15.5x23.5 cm
Disponible chez l'éditeur (délai d'approvisionnement : 15 jours).
Prix indicatif 63,29 €
Ajouter au panierThème de Descriptional Complexity of Formal Systems :
Mots-clés :
automata; automata theory; automation; computational linguistics; computer science; computer systems; context free languages; databases; engineering; finite automata; finite state automata; formal languages; linguistics; mathematics; probability; query languages; regular languages; state complexity; theoretical computer science; translation (languages)