Masami Ito, Masafumi Toyama
Proceedings of the 12th International Conference on Developments in Language Theory
DLT, 2008.

@proceedings{DLT-2008,
	address       = "Kyoto, Japan",
	editor        = "Masami Ito and Masafumi Toyama",
	isbn          = "978-3-540-85779-2",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 12th International Conference on Developments in Language Theory}",
	volume        = 5257,
	year          = 2008,
}

Contents (42 items)

14 ×#automaton
9 ×#on the
7 ×#complexity
7 ×#finite
5 ×#regular expression
4 ×#decidability
4 ×#word
3 ×#problem
3 ×#sequence
2 ×#ambiguity

DLT-2008-Esik

Iteration Semirings (ZÉ), pp. 1–20.

DLT-2008-Hirvensalo #aspect-oriented #automaton #finite #quantum

Various Aspects of Finite Quantum Automata (MH), pp. 21–33.

DLT-2008-HromkovicS #automaton #bound #nondeterminism #on the #proving

On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes (JH, GS), pp. 34–55.

DLT-2008-Jancar #decidability #similarity

Selected Ideas Used for Decidability and Undecidability of Bisimilarity (PJ), pp. 56–71.

DLT-2008-Shallit #problem

The Frobenius Problem and Its Generalizations (JS), pp. 72–83.

DLT-2008-DAlessandroV #formal method

Well Quasi-orders in Formal Language Theory (FD, SV), pp. 84–95.

DLT-2008-Ada #communication #complexity #nondeterminism #on the #regular expression

On the Non-deterministic Communication Complexity of Regular Languages (AA), pp. 96–107.

DLT-2008-AllauzenMR #algorithm #ambiguity #automaton #finite #testing

General Algorithms for Testing the Ambiguity of Finite Automata (CA, MM, AR), pp. 108–120.

DLT-2008-AtigBH #automaton #multi

Emptiness of Multi-pushdown Automata Is 2ETIME-Complete (MFA, BB, PH), pp. 121–133.

DLT-2008-BassinoGN #complexity #finite #linear #set #word

The Average State Complexity of the Star of a Finite Set of Words Is Linear (FB, LG, CN), pp. 134–145.

DLT-2008-BordihnKM #automaton #capacity #communication #finite #on the #parallel

On the Computational Capacity of Parallel Communicating Finite Automata (HB, MK, AM), pp. 146–157.

DLT-2008-BucciLL #morphism #on the #standard

On a Generalization of Standard Episturmian Morphisms (MB, AdL, ADL), pp. 158–169.

DLT-2008-CaludeNSS #recursion #set #string

Universal Recursively Enumerable Sets of Strings (CSC, AN, LS, FS), pp. 170–182.

DLT-2008-CaludeZ #independence #sequence

Algorithmically Independent Sequences (CSC, MZ), pp. 183–195.

DLT-2008-CassaigneKZ #complexity #sequence

Relationally Periodic Sequences and Subword Complexity (JC, TK, LQZ), pp. 196–205.

DLT-2008-CrochemoreFIJ #bound #string

Bounds on Powers in Strings (MC, SZF, CSI, IJ), pp. 206–215.

DLT-2008-CsimaK #decidability #question #reachability

When Is Reachability Intrinsically Decidable? (BFC, BK), pp. 216–227.

DLT-2008-Csuhaj-VarjuDV

Some New Modes of Competence-Based Derivations in CD Grammar Systems (ECV, JD, GV), pp. 228–239.

DLT-2008-CarpiD #automaton #problem #transitive

The Synchronization Problem for Strongly Transitive Automata (AC, FD), pp. 240–251.

DLT-2008-Souza #decidability #equivalence #on the #transducer

On the Decidability of the Equivalence for k-Valued Transducers (RdS), pp. 252–263.

DLT-2008-DennunzioF #2d #automaton #decidability

Decidable Properties of 2D Cellular Automata (AD, EF), pp. 264–275.

DLT-2008-DurandRS #fixpoint

Fixed Point and Aperiodic Tilings (BD, AER, AS), pp. 276–288.

DLT-2008-EngelfrietLM #bottom-up #multi #transducer

Extended Multi Bottom-Up Tree Transducers (JE, EL, AM), pp. 289–300.

DLT-2008-EsparzaKL #analysis #fixpoint

Derivation Tree Analysis for Accelerated Fixed-Point Computation (JE, SK, ML), pp. 301–313.

DLT-2008-FiliotTT #automaton #constraints

Tree Automata with Global Constraints (EF, JMT, ST), pp. 314–326.

DLT-2008-FreydenbergerR #problem

Bad News on Decision Problems for Patterns (DDF, DR), pp. 327–338.

DLT-2008-GawrychowskiKRS #context-free grammar #polynomial

Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time (PG, DK, NR, JS), pp. 339–358.

DLT-2008-GeffertMP #automaton #regular expression #representation

More Concise Representation of Regular Languages by Automata and Regular Expressions (VG, CM, BP), pp. 359–370.

DLT-2008-Glockler #automaton #taxonomy

A Taxonomy of Deterministic Forgetting Automata (JG), pp. 371–382.

DLT-2008-GruberH #automaton #finite #regular expression

Provably Shorter Regular Expressions from Deterministic Finite Automata (HG, MH), pp. 383–395.

DLT-2008-HadravovaH #scalability #similarity #word

Large Simple Binary Equality Words (JH, SH), pp. 396–407.

DLT-2008-HolubN #finite #on the #word

On the Relation between Periodicity and Unbordered Factors of Finite Words (SH, DN), pp. 408–418.

DLT-2008-ItoKKS #sequence

Duplication in DNA Sequences (MI, LK, ZK, SS), pp. 419–430.

DLT-2008-Jiraskova #complexity #on the #regular expression

On the State Complexity of Complements, Stars, and Reversals of Regular Languages (GJ), pp. 431–442.

DLT-2008-JiraskovaO #automaton #complexity #finite #on the

On the State Complexity of Operations on Two-Way Finite Automata (GJ, AO), pp. 443–454.

DLT-2008-KapoutsisKM #automaton #complexity #on the

On the Size Complexity of Rotating and Sweeping Automata (CAK, RK, TM), pp. 455–466.

DLT-2008-KarhumakiS #analysis #theorem

An Analysis and a Reproof of Hmelevskii’s Theorem (JK, AS), pp. 467–478.

DLT-2008-KlimaP

Hierarchies of Piecewise Testable Languages (OK, LP), pp. 479–490.

DLT-2008-KuskeM #automaton #regular expression

Construction of Tree Automata from Regular Expressions (DK, IM), pp. 491–503.

DLT-2008-MantaciMR #word

Balance Properties and Distribution of Squares in Circular Words (RM, SM, AR), pp. 504–515.

DLT-2008-Morin #ambiguity #logic

MSO Logic for Unambiguous Shared-Memory Systems (RM), pp. 516–528.

DLT-2008-SelivanovW #complexity

Complexity of Topological Properties of Regular ω-Languages (VLS, KWW), pp. 529–542.