A Second Course in Formal Languages and Automata Theory
From MaRDI portal
Publication:3549457
DOI10.1017/CBO9780511808876zbMath1163.68025OpenAlexW1485181793MaRDI QIDQ3549457
Publication date: 23 December 2008
Full work available at URL: https://doi.org/10.1017/cbo9780511808876
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Combinatorics on words (68R15) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items
State complexity of permutation on finite languages over a binary alphabet ⋮ The State Complexity of Lexicographically Smallest Words and Computing Successors ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ A linear-time simulation of deterministic \(d\)-limited automata ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ On the joint subword complexity of automatic sequences ⋮ Factorization in Formal Languages ⋮ State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ Unnamed Item ⋮ Periodicity in rectangular arrays ⋮ Automatic sequences and curves over finite fields ⋮ Duplications and Pseudo-Duplications ⋮ Translating between models of concurrency ⋮ From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods ⋮ State Complexity of Prefix Distance ⋮ Outfix-guided insertion ⋮ Automatic sequences: from rational bases to trees ⋮ Unnamed Item ⋮ On extended boundary sequences of morphic and Sturmian words ⋮ State complexity of the concatenation of regular tree languages ⋮ Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages ⋮ Existential and universal width of alternating finite automata ⋮ Lengths of words accepted by nondeterministic finite automata ⋮ State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ General Framework ⋮ Number of holes in unavoidable sets of partial words. II. ⋮ Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ The range of non-linear natural polynomials cannot be context-free ⋮ From Combinatorial Games to Shape-Symmetric Morphisms ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Nondeterministic automatic complexity of overlap-free and almost square-free words ⋮ On Language Decompositions and Primality ⋮ Profinite automata ⋮ Reducing complex CSP models to traces via priority ⋮ AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY ⋮ Unnamed Item ⋮ Pseudo-inversion: closure properties and decidability ⋮ Consensus String Problem for Multiple Regular Languages ⋮ FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Binary codes that do not preserve primitivity ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Descriptional Complexity of Error Detection ⋮ Unique decipherability in formal languages ⋮ Remarks on Separating Words ⋮ State Trade-Offs in Unranked Tree Automata ⋮ On the Language of Primitive Partial Words ⋮ State complexity of deletion and bipolar deletion ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ State Complexity of Suffix Distance ⋮ Cobham’s Theorem and Automaticity ⋮ The number of languages with maximum state complexity ⋮ Outfix-Guided Insertion ⋮ DIGIT SUMS AND VERTEX-LABELINGS ⋮ Quasi-Distances and Weighted Finite Automata ⋮ State Complexity of Prefix Distance of Subregular Languages ⋮ Prefix Distance Between Regular Languages ⋮ Languages, Decidability, and Complexity ⋮ Nondeterministic Tree Width of Regular Languages ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Site-directed insertion: language equations and decision problems ⋮ Undecidability of state complexity ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Unnamed Item ⋮ A formalisation of the Myhill-Nerode theorem based on regular expressions ⋮ Union-complexities of Kleene plus operation ⋮ Operational union-complexity ⋮ State complexity of prefix distance
