Han / Ko Descriptional Complexity of Formal Systems
Erscheinungsjahr 2022
ISBN: 978-3-030-93489-7
Verlag: Springer International Publishing
Format: PDF
Kopierschutz: 1 - PDF Watermark
23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings
E-Book, Englisch, 201 Seiten
Reihe: Lecture Notes in Computer Science
ISBN: 978-3-030-93489-7
Verlag: Springer International Publishing
Format: PDF
Kopierschutz: 1 - PDF Watermark
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.
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
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.
