Hsu-Chun Yen, Oscar H. Ibarra
Proceedings of the 16th International Conference on Developments in Language Theory
DLT, 2012.

@proceedings{DLT-2012,
	address       = "Taipei, Taiwan",
	doi           = "10.1007/978-3-642-31653-1",
	editor        = "Hsu-Chun Yen and Oscar H. Ibarra",
	isbn          = "978-3-642-31652-4",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 16th International Conference on Developments in Language Theory}",
	volume        = 7410,
	year          = 2012,
}

Contents (43 items)

11 ×#automaton
6 ×#context-free grammar
5 ×#regular expression
5 ×#word
4 ×#finite
4 ×#on the
3 ×#nondeterminism
3 ×#theorem
2 ×#bound
2 ×#complexity

DLT-2012-Szilard

The Kind Hearted Dragon Prof. Sheng Yu, 1950-2012 (AS), pp. 1–6.

DLT-2012-Csuhaj-Varju #automaton

P and dP Automata: Unconventional versus Classical Automata (ECV), pp. 7–22.

DLT-2012-Iwama #quantum #string

Recovering Strings in Oracles: Quantum and Classic (KI), p. 23.

DLT-2012-HromkovicKKS #automaton #logic #nondeterminism #representation

Determinism vs. Nondeterminism for Two-Way Automata — Representing the Meaning of States by Logical Formulæ (JH, RK, RK, RS), pp. 24–39.

DLT-2012-Kari #automaton

Cellular Automata, the Collatz Conjecture and Powers of 3/2 (JK), pp. 40–49.

DLT-2012-BrzozowskiT #regular expression

Quotient Complexities of Atoms of Regular Languages (JAB, HT), pp. 50–61.

DLT-2012-BealCDJL #decidability #geometry #regular expression

Decidability of Geometricity of Regular Languages (MPB, JMC, JPD, HJ, SL), pp. 62–72.

DLT-2012-Schmid #regular expression

Inside the Class of REGEX Languages (MLS), pp. 73–84.

DLT-2012-HanKS #context-free grammar #regular expression

Computing the Edit-Distance between a Regular Language and a Context-Free Language (YSH, SKK, KS), pp. 85–96.

DLT-2012-0002HOT #context-free grammar #problem #word

Semigroups with a Context-Free Word Problem (MH, DFH, MDO, RMT), pp. 97–108.

DLT-2012-HolzerJM #context-free grammar

Generalized Derivations with Synchronized Context-Free Grammars (MH, SJ, IM), pp. 109–120.

DLT-2012-Okhotin #theorem

Non-erasing Variants of the Chomsky-Schützenberger Theorem (AO), pp. 121–129.

DLT-2012-ReidenbachS #pattern matching

Regular and Context-Free Pattern Languages over Small Alphabets (DR, MLS), pp. 130–141.

DLT-2012-EsikO #context-free grammar #on the #word

On Context-Free Languages of Scattered Words (ZÉ, SO), pp. 142–153.

DLT-2012-LehtinenO #context-free grammar #morphism

Homomorphisms Preserving Deterministic Context-Free Languages (TL, AO), pp. 154–165.

DLT-2012-GeffertP

Unary Coded NP-Complete Languages in ASPACE (log log n) (VG, DP), pp. 166–177.

DLT-2012-KrebsL

Dense Completeness (AK, KJL), pp. 178–189.

DLT-2012-HolzerJ #automaton #equivalence #fault

From Equivalence to Almost-Equivalence, and Beyond — Minimizing Automata with Errors — (MH, SJ), pp. 190–201.

DLT-2012-KapoutsisL #automaton #finite #nondeterminism #theorem

Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata (CAK, NL), pp. 202–213.

DLT-2012-KutribMW #automaton #finite #multi

States and Heads Do Count for Unary Multi-head Finite Automata (MK, AM, MW), pp. 214–225.

DLT-2012-CaralpRT #automaton #bound #multi

Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness (MC, PAR, JMT), pp. 226–238.

DLT-2012-CadilhacFM #ambiguity #automaton

Unambiguous Constrained Automata (MC, AF, PM), pp. 239–250.

DLT-2012-PrusaM #2d #automaton

Two-Dimensional Sgraffito Automata (DP, FM), pp. 251–262.

DLT-2012-Carton #transducer

Two-Way Transducers with a Two-Way Output Tape (OC), pp. 263–272.

DLT-2012-BoiretLN #learning

Learning Rational Functions (AB, AL, JN), pp. 273–283.

DLT-2012-LavadoPS #automaton #context-free grammar #nondeterminism

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata (GJL, GP, SS), pp. 284–295.

DLT-2012-KarhumakiPS #theorem

Fine and Wilf’s Theorem for k-Abelian Periods (JK, SP, AS), pp. 296–307.

DLT-2012-MasseGH #pseudo #word

Pseudoperiodic Words (ABM, SG, SH), pp. 308–319.

DLT-2012-DennunzioFP

Acceptance Conditions for ω-Languages (AD, EF, JP), pp. 320–331.

DLT-2012-ChenL #regular expression

Checking Determinism of Regular Expressions with Counting (HC, PL), pp. 332–343.

DLT-2012-KlimaP #automaton

Biautomata for k-Piecewise Testable Languages (OK, LP), pp. 344–355.

DLT-2012-Otto #component #on the

On Centralized PC Grammar Systems with Context-Sensitive Components (FO), pp. 356–367.

DLT-2012-BuchseMV #semantics

Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars (MB, AM, HV), pp. 368–379.

DLT-2012-JiraskovaS #complexity

The State Complexity of Star-Complement-Star (GJ, JS), pp. 380–391.

DLT-2012-GandhiKL #complexity #finite #on the #word

On State Complexity of Finite Word and Tree Languages (AG, BK, JL), pp. 392–403.

DLT-2012-Blanchet-SadriJM #word

Squares in Binary Partial Words (FBS, YJ, JMM), pp. 404–415.

DLT-2012-ManeaMN #permutation

The Avoidability of Cubes under Permutations (FM, MM, DN), pp. 416–427.

DLT-2012-FazekasMS #bound

Hairpin Completion with Bounded Stem-Loop (SZF, RM, KST), pp. 428–439.

DLT-2012-NevisiR #reduction

Morphic Primitivity and Alphabet Reductions (HN, DR), pp. 440–451.

DLT-2012-FlickK #on the

On a Hierarchy of Languages with Catenation and Shuffle (NEF, MK), pp. 452–458.

DLT-2012-KetemaS #normalisation #string #termination

Characterizing Languages by Normalization and Termination in String Rewriting — (JK, JGS), pp. 459–464.

DLT-2012-SaloT #geometry

Geometry and Dynamics of the Besicovitch and Weyl Spaces (VS, IT), pp. 465–470.

DLT-2012-GiambrunoMNS #bidirectional #finite

A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay (LG, SM, JN, CS), pp. 471–476.