Language and Automata Theory and Applications

1. Front Matter

   Pages i-xi

   PDF

2. Invited Papers

   1. Front Matter

      Pages 1-1

      PDF

   2. The New Complexity Landscape Around Circuit Minimization

      • Eric Allender

      Pages 3-16

   3. Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases

      • Laure Daviaud

      Pages 17-32

   4. Approaching Arithmetic Theories with Finite-State Automata

      • Christoph Haase

      Pages 33-43

   5. Recompression: Technique for Word Equations and Compressed Data

      • Artur Jeż

      Pages 44-67

   6. How to Prove that a Language Is Regular or Star-Free?

      • Jean-Éric Pin

      Pages 68-88

   7. Deciding Classes of Regular Languages: The Covering Approach

      • Thomas Place

      Pages 89-112

3. Algebraic Structures

   1. Front Matter

      Pages 113-113

      PDF

   2. Nonstandard Cayley Automatic Representations for Fundamental Groups of Torus Bundles over the Circle

      • Dmitry Berdinsky, Prohrak Kruengthomya

      Pages 115-127

   3. \(\langle \mathbb {R}, +,<,1 \rangle \) Is Decidable in \(\langle \mathbb {R}, +,< ,\mathbb {Z}\rangle \)

      • Alexis Bès, Christian Choffrut

      Pages 128-140

   4. Ordered Semiautomatic Rings with Applications to Geometry

      • Ziyuan Gao, Sanjay Jain, Ji Qi, Philipp Schlicht, Frank Stephan, Jacob Tarr

      Pages 141-153

4. Automata

   1. Front Matter

      Pages 155-155

      PDF

   2. Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions

      • Siddharth Bhaskar, Jane Chandlee, Adam Jardine, Christopher Oakden

      Pages 157-169

   3. Expressiveness and Conciseness of Timed Automata for the Verification of Stochastic Models

      • Susanna Donatelli, Serge Haddad

      Pages 170-183

   4. Windable Heads and Recognizing NL with Constant Randomness

      • Mehmet Utkan Gezer

      Pages 184-195

   5. Alternating Finite Automata with Limited Universal Branching

      • Chris Keeler, Kai Salomaa

      Pages 196-207

   6. Pebble-Intervals Automata and FO\(^2\) with Two Orders

      • Nadia Labai, Tomer Kotek, Magdalena Ortiz, Helmut Veith

      Pages 208-221

   7. Limited Two-Way Deterministic Finite Automata with Advice

      • Ahmet Bilal Uçan

      Pages 222-232

5. Complexity

   1. Front Matter

      Pages 233-233

      PDF

This book constitutes the proceedings of the 14th International Conference on Language and Automata Theory and Applications, LATA 2020, which was planned to be held in Milan, Italy, in March 2020. Due to the corona pandemic, the actual conference was postponed and will be held together with LATA 2021.
The 26 full papers presented in this volume were carefully reviewed and selected from 59 submissions. They were organized in topical sections named: algebraic structures; automata; complexity; grammars; languages; trees and graphs; and words and codes. The book also contains 6 invited papers in full-paper length. 

• artificial intelligence
• automata
• automata theory
• computational linguistics
• computer hardware
• computer programming
• computer systems
• context free languages
• databases
• engineering
• finite automata
• formal languages
• graph theory
• linguistics
• mathematics
• microprocessor chips
• Natural Language Processing (NLP)
• semantics
• theoretical computer science
• translation (languages)
• algorithm analysis and problem complexity

• University of Milano-Bicocca, Milan, Italy

  Alberto Leporati, Claudio Zandron

• Rovira i Virgili University, Tarragona, Spain

  Carlos Martín-Vide

• Ariel University, Ariel, Israel

  Dana Shapira

Policies and ethics