دانلود کتاب Developments in Language Theory: 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008. Proceedings

فهرست مطالب :

Front Matter....Pages -
Iteration Semirings....Pages 1-20
Various Aspects of Finite Quantum Automata....Pages 21-33
On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes....Pages 34-55
Selected Ideas Used for Decidability and Undecidability of Bisimilarity....Pages 56-71
The Frobenius Problem and Its Generalizations....Pages 72-83
Well Quasi-orders in Formal Language Theory....Pages 84-95
On the Non-deterministic Communication Complexity of Regular Languages....Pages 96-107
General Algorithms for Testing the Ambiguity of Finite Automata....Pages 108-120
Emptiness of Multi-pushdown Automata Is 2ETIME-Complete....Pages 121-133
The Average State Complexity of the Star of a Finite Set of Words Is Linear....Pages 134-145
On the Computational Capacity of Parallel Communicating Finite Automata....Pages 146-157
On a Generalization of Standard Episturmian Morphisms....Pages 158-169
Universal Recursively Enumerable Sets of Strings....Pages 170-182
Algorithmically Independent Sequences....Pages 183-195
Relationally Periodic Sequences and Subword Complexity....Pages 196-205
Bounds on Powers in Strings....Pages 206-215
When Is Reachability Intrinsically Decidable?....Pages 216-227
Some New Modes of Competence-Based Derivations in CD Grammar Systems....Pages 228-239
The Synchronization Problem for Strongly Transitive Automata....Pages 240-251
On the Decidability of the Equivalence for k -Valued Transducers....Pages 252-263
Decidable Properties of 2D Cellular Automata....Pages 264-275
Fixed Point and Aperiodic Tilings....Pages 276-288
Extended Multi Bottom-Up Tree Transducers....Pages 289-300
Derivation Tree Analysis for Accelerated Fixed-Point Computation....Pages 301-313
Tree Automata with Global Constraints....Pages 314-326
Bad News on Decision Problems for Patterns....Pages 327-338
Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time....Pages 339-358
More Concise Representation of Regular Languages by Automata and Regular Expressions....Pages 359-370
A Taxonomy of Deterministic Forgetting Automata....Pages 371-382
Provably Shorter Regular Expressions from Deterministic Finite Automata....Pages 383-395
Large Simple Binary Equality Words....Pages 396-407
On the Relation between Periodicity and Unbordered Factors of Finite Words....Pages 408-418
Duplication in DNA Sequences....Pages 419-430
On the State Complexity of Complements, Stars, and Reversals of Regular Languages....Pages 431-442
On the State Complexity of Operations on Two-Way Finite Automata....Pages 443-454
On the Size Complexity of Rotating and Sweeping Automata....Pages 455-466
An Analysis and a Reproof of Hmelevskii’s Theorem....Pages 467-478
Hierarchies of Piecewise Testable Languages....Pages 479-490
Construction of Tree Automata from Regular Expressions....Pages 491-503
Balance Properties and Distribution of Squares in Circular Words....Pages 504-515
MSO Logic for Unambiguous Shared-Memory Systems....Pages 516-528
Complexity of Topological Properties of Regular ω -Languages....Pages 529-542
Back Matter....Pages -