Language and Automata Theory and Applications: 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010, Proceedings / Edition 1

Language and Automata Theory and Applications: 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010, Proceedings / Edition 1

by Carlos Martin-Vide, Henning Fernau, Adrian Horia Dediu
     
 

ISBN-10: 3642130887

ISBN-13: 9783642130885

Pub. Date: 05/10/2010

Publisher: Springer Berlin Heidelberg

This book constitutes the proceedings of the 4th International Conference, LATA 2010, held in May 2010 in Trier, Germany. The 47 full papers presented were carefully selected from 115 submissions and focus on topics such as algebraic language theory , algorithmic learning, bioinformatics, computational biology, pattern recognition, program verification, term

…  See more details below

Overview

This book constitutes the proceedings of the 4th International Conference, LATA 2010, held in May 2010 in Trier, Germany. The 47 full papers presented were carefully selected from 115 submissions and focus on topics such as algebraic language theory , algorithmic learning, bioinformatics, computational biology, pattern recognition, program verification, term rewriting and tree machines.

Product Details

ISBN-13:
9783642130885
Publisher:
Springer Berlin Heidelberg
Publication date:
05/10/2010
Series:
Lecture Notes in Computer Science / Theoretical Computer Science and General Issues Series, #6031
Edition description:
2010
Pages:
622
Product dimensions:
6.20(w) x 9.20(h) x 1.30(d)

Table of Contents

Invited Talks

Complexity in Convex Languages Janusz Brzozowski 1

Three Learnable Models for the Description of Language Alexander Clark 16

Arbology: Trees and Pushdown Automata Borivoj Melichar 32

Analysis of Communicating Automata Anca Muscholl 50

Regular Papers

Complexity of the Satisfiability Problem for a Class of Propositional Schemata Vincent Aravantinos Ricardo Caferra Nicolas Peltier 58

A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton Pablo Arrighi Jonathan Grattage 70

A Fast Longest Common Subsequence Algorithm for Similar Strings Abdullah N. Arslan 82

Abelian Square-Free Partial Words Francine Blanchet-Sadri Jane I. Kim Robert Mercas William Severa Sean Simmons 94

Avoidable Binary Patterns in Partial Words Francine Blanchet-Sadri Robert Mercas Sean Simmons Eric Weissenstein 106

Equivalence and Inclusion Problem for Strongly Unambiguous Böchi Automata Nicolas Bousquet Christof Löding 118

Pregroup Grammars with Letter Promotions Wojciech Buszkowski Zhe Lin 130

A Hierarchical Classification of First-Order Recurrent Neural Networks Jérémie Cabessa Alessandro E.P. Villa 142

Choosing Word Occurrences for the Smallest Grammar Problem Rafael Carrascosa François Coste Matthias Gallé Gabriel Infante-Lopez 154

Agreement and Cliticization in Italian: A Pregroup Analysis Claudia Casadio 166

Geometricity of Binary Regular Languages Jean-Marc Champarnaud Jean-Philippe Dubernard Hadrien Jeanne 178

On the Expressive Power of FO[+] Christain Choffrut Andreas Malcher Carlo Mereghetti Beatrice Palano 190

Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach Christophe Costa Florêncio Henning Fernau 202

Operator Precedence and the Visibly Pushdown Property Stefano Crespi Reghizzi Dino Mandrioli 214

On the Maximal Number of Cubic Runs in a String Maxime Crochemore Costas Iliopoulos Marcin Kubica Jakub Radoszewski Wojciech Rytter Tomasz Walen 227

On the Hamiltonian Operators for Adiabatic Quantum Reduction of SAT William Cruz-Santos Guillermo Morales-Luna 239

Parametric Metric Interval Temporal Logic Barbara Di Giampaolo Salvatore La Torre Margherita Napoli 249

Short Witnesses and Accepting Lassos in ω-Automata Rüdiger Ehlers 261

Grammar-Based Compression in a Streaming Model Travis Gagie Pawel Gawrychowski 273

Simplifying Regular Expressions: A Quantitative Perspective Hermann Gruber Stefan Gulan 285

A Programming Language Tailored to the Specification and Solution of Differential Equations Describing Processes on Networks Reinhard Hemmerling Katarína Smolenová Winfried Kurth 297

The Inclusion Problem for Regular Expressions Dag Hovland 309

Learnability of Automatic Classes Sanjay Jain Qinglong Luo Frank Stephan 321

Untestable Properties Expressible with Four First-Order Quantifiers Charles Jordan Thomas Zeugmann 333

The Copying Power of Well-Nested Multiple Context-Free Grammars Makoto Kanazawa Sylvain Salvati 344

Post Correspondence Problem with Partially Commutative Alphalbets Barbara Klunder Wojciech Rytter 356

Reversible Pushdown Automata Martin Kutrib Andreas Malcher 368

String Extension Learning Using Lattices Anna Kasprzik Timo Kötzing 380

The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape Alexander A. Letichevsky Arsen S. Shoukourian Samvel K. Shoukourian 392

Primitive Words are Unavoidable for Coutext-Free Languages Peter Leupold 403

Model Nonassociative Lambek Calculus with Assumptions: Complexity and Context-Freeness Zhe Lin 414

Hard Counting Problems for Partial Words Florin Manea Catalin Tiseanu 426

Exact Analysis of Horspool's and Sunday's Pattern Matching Algorithms with Probabilistic Arithmetic Automata Tobias Marschall Sven Rahmann 439

SA-REPC - Sequence Alignment with Regular Expression Path Constraint Nimrod Milo Tamar Pinhas Michal Ziv-Ukelson 451

CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages Benedek Nagy Friedrich Otto 463

A Boundary between Universality and Non-universality in Extended Spiking Neural P Systems Turlough Neary 475

Using Sums-of-Products for Non-standard Reasoning Rafael Peñaloza 488

Restarting Automata with Structured Output and Functional Generative Description Martin Plátek František Mráz Markéta Lopatková 500

A Randomized Numerical Aligner (rNA) Alberto Policriti Alexandru I. Tomescu Francesco Vezzi 512

Language-Based Comparison of Petri Nets with Black Tokens, Pure Names and Ordered Data Fernando Rosa-Velardo Giorgio Delzanno 524

Verifying Complex Continuous Real-Time Systems with Coinductive CLP(R) Neda Saeedloei Gopal Gupta 536

Incremental Building in Peptide Computing to Solve Hamiltonian Path Problem Muthiah Sakthi Balan Parameswaran Seshan 549

Variable Automata over Infinite Alphabets Orna Grumberg Orna Kupferman Sarai Sheinvald 561

Some Minimality Results on Biresidual and Biseparable Automata Hellis Tamm 573

Extending Stochastic Context-Free Grammars for an Application in Bioinformatics Frank Weinberg Markus E. Nebel 585

Chomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages Ryo Yoshinaka Yuichi Kaji Hiroyuki Seki 596

Complexity of Guided Insertion-Deletion in RNA-Editing Hans Zantema 608

Author Index 621

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >