| Document Type
|
:
|
BL
|
| Record Number
|
:
|
861066
|
| Main Entry
|
:
|
LATA (Conference)(13th :2019 :, Saint Petersburg, Russia)
|
| Title & Author
|
:
|
Language and Automata Theory and Applications : : 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings /\ Carlos Martín-Vide, Alexander Okhotin, Dana Shapira (eds.).
|
| Publication Statement
|
:
|
Cham, Switzerland :: Springer,, 2019.
|
| Series Statement
|
:
|
Lecture notes in computer science ;; 11417
|
|
|
:
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues
|
| Page. NO
|
:
|
1 online resource (xvii, 470 pages) :: illustrations (some color)
|
| ISBN
|
:
|
3030134342
|
|
|
:
|
: 3030134350
|
|
|
:
|
: 9783030134341
|
|
|
:
|
: 9783030134358
|
|
|
:
|
9783030134341
|
| Notes
|
:
|
International conference proceedings.
|
| Bibliographies/Indexes
|
:
|
Includes bibliographical references and author index.
|
| Contents
|
:
|
Intro; Preface; Organization; Abstracts of Invited Papers; Searching and Indexing Compressed Text; Pattern Discovery in Biological Sequences; Contents; Invited Papers; Modern Aspects of Complexity Within Formal Languages; 1 Introduction; 2 Some Modern Concepts of Complexity Theory; 3 First Case Study: String-to-String Correction S2S; 4 Second Case Study: Grammar-Based Compression; 5 Third Case Study: Synchronizing Words; 6 Fourth Case Study: Consistency Problem for DFAs; 7 Fifth Case Study: Lower Bounds for Universality; 8 Sixth Case Study: Parsing Theory; 9 Conclusions; References
|
|
|
:
|
4 Main TheoremReferences; Decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular Automata; 1 Introduction; 2 Higher-Order CA and Linear CA; 3 Dynamical Properties; 4 Sensitivity of Frobenius LCA over Znpk; 5 Conclusions; References; On Varieties of Ordered Automata; 1 Introduction; 2 Ordered Automata; 3 Positive C-Varieties of Ordered Semiautomata; 4 Examples; 4.1 Counter-Free Automata; 4.2 Acyclic Automata; 4.3 Acyclic Confluent Automata; 4.4 Ordered Automata with Extensive Actions; 4.5 Autonomous Automata; 4.6 Synchronizing and Weakly Confluent Automata
|
|
|
:
|
4 The One-Way Polynomial-Size Oracle Hierarchy5 A Characterization for the Alternating Hierarchy; 6 Conclusion; References; Orbits of Abelian Automaton Groups; 1 Introduction; 2 Background; 2.1 Automata and Automaton Groups; 2.2 Abelian Automata; 3 Affine Residuation Parametrization; 3.1 Residuation Pairs; 3.2 Number Field Embedding; 4 Orbit Rationality; 4.1 Background; 4.2 The Abelian Case; 4.3 Decision Procedure; 5 Discussion and Open Problems; References; Bounded Automata Groups are co-ET0L; 1 Introduction; 2 ET0L Languages and CSPD Automata; 2.1 CSPD Automata; 3 Bounded Automata Groups
|
|
|
:
|
4.7 Automata for Languages Closed Under Inserting Segments4.8 Automata for Finite and Prefix-Testable Languages; 5 Membership Problem for C-Varieties of Semiautomata; References; Automata over Infinite Sequences of Reals; 1 Introduction; 2 The Automaton Model; 3 Periodic Muller R-automata; 4 A Logic for Periodic R-automata; 4.1 From Periodic R-automata to Formulas; 4.2 From MSOR Logic to Periodic Automata; References; Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice; 1 Prelude: Quick Overview
|
|
|
:
|
Observation and Interaction1 Interaction vs. Observation; References; From Words to Graphs, and Back; 1 Introduction; 2 Words, Graphs and Well-quasi-ordering; 2.1 An Introductory Example; 2.2 Geometric Grid Classes of Permutations and Letter Graphs; 2.3 Deciding WQO; 3 Representing Graphs by Words; 3.1 Entropy of Hereditary Properties; 3.2 Coding of Graphs in Classes of High Speed; 3.3 Representing Graphs in Hereditary Classes of Low Speed; References; Automata; An Oracle Hierarchy for Small One-Way Finite Automata; 1 Introduction; 2 Preparation; 3 Oracle-1NFAs
|
| Abstract
|
:
|
This book constitutes the refereed proceedings of the 13th International Conference on Language and Automata Theory and Applications, LATA 2019, held in St. Petersburg, Russia, in March 2019. The 31 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 98 submissions. The papers cover the following topics: Automata; Complexity; Grammars; Languages; Graphs, trees and rewriting; and Words and codes.
|
| Subject
|
:
|
Formal languages, Congresses.
|
| Subject
|
:
|
Machine theory, Congresses.
|
| Subject
|
:
|
Mathematical linguistics, Congresses.
|
| Subject
|
:
|
Formal languages.
|
| Subject
|
:
|
Machine theory.
|
| Subject
|
:
|
Mathematical linguistics.
|
| Dewey Classification
|
:
|
005.101/5113
|
| LC Classification
|
:
|
QA267.L38 2019eb
|
| Added Entry
|
:
|
Martín Vide, Carlos
|
|
|
:
|
Okhotin, Alexander
|
|
|
:
|
Shapira, Dana
|
| Parallel Title
|
:
|
LATA 2019
|