|
" Language equations "
Ernst L. Leiss.
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
738654
|
| Doc. No
|
:
|
b558567
|
| Main Entry
|
:
|
Ernst L. Leiss.
|
| Title & Author
|
:
|
Language equations\ Ernst L. Leiss.
|
| Publication Statement
|
:
|
New York: Springer Science+Business Media, [1999] ©1999
|
| Series Statement
|
:
|
Monographs in computer science.
|
| Page. NO
|
:
|
(xvi, 216 pages)
|
| ISBN
|
:
|
1461221560
|
|
|
:
|
: 1461274362
|
|
|
:
|
: 9781461221562
|
|
|
:
|
: 9781461274360
|
| Contents
|
:
|
1.1 Arithmetic Equations 2 --;1.2 Language Equations 3 --;1.4 Nonlinear Equations 5 --;1.5 Invertibility of Operations 6 --;1.6 Implicit and Explicit Equations 6 --;1.8 Assumed Background of the Reader 9 --;2 Basic Definitions 10 --;2.1 The Alphabet 10 --;2.2 The Constant Languages 11 --;2.3 The Language Operations 11 --;2.4 The Variables 13 --;2.5 The Expressions 13 --;2.6 The Equations 15 --;2.6.1 Two-Sided Equations 16 --;2.6.2 Explicit and Implicit Equations 16 --;2.7 The Relations 17 --;3 Classical Language Equations and the Substitution Property 21 --;3.2 The Syntactic Solution Approach 23 --;3.3 The Substitution Property 28 --;3.4 Constructing Nondeterministic Finite Automata for the Solution Languages 31 --;3.5 A Note on Context-Free Grammars 34 --;4 Boolean Language Equations 38 --;4.1 Boolean Automata 39 --;4.2 The & lambda;-Property and the Normal Form Theorem 42 --;4.3 The Uniqueness Criterion for Boolean Equations 46 --;4.4 Generalized Derivatives of Expressions 47 --;4.5 Constructing a Boolean Automaton for the Solution of Boolean Equations 50 --;4.6 Boolean Equations with Multiple Solution 60 --;5 More on Generalized Derivatives 64 --;5.1 Derivatives and the & lambda;-Property 64 --;5.2 Existence and Uniqueness of Solutions 69 --;5.4 Techniques for Determining Whether a Word Is in a Solution 75 --;6 Star Equations 79 --;7 Explicit Equations over a One-Letter Alphabet 86 --;7.1 Properties of Languages over a One-Letter Alphabet 87 --;7.2 Normal Forms of Expressions Without Complementation 89 --;7.3 Two Key Theorems 91 --;7.4 Solving General Equations in One Variable 99 --;7.5 Solving Systems of Equations 101 --;7.6 Uniqueness and Regularity of Solutions 102 --;7.6.1 Uniqueness 102 --;7.6.2 Regularity 103 --;7.6.3 CFL over {a} 104 --;7.7 Explicit Equations over {a} with Complementation 105 --;8 Implicit Equations with Union and Left-Concatenation 109 --;8.1 Basic Properties of Implicit Language Equations 111 --;8.1.1 Existence of Solutions 111 --;8.1.2 Nonclosure of CFL Under Implicit Language Equations 112 --;8.2 A Procedure for Determining That No Solution Exists 114 --;8.3 Solving Implicit Language Equations 116 --;8.4 Characterizing Uniqueness in Implicit Language Equations 121 --;9 Regular Implicit Equations over a One-Letter Alphabet with Union, Concatenation, and Star 129 --;9.1 Properties of Expressions over a One-Letter Alphabet 130 --;9.2 Solving One Equation in One Variable 133 --;9.3 Solving Systems of Equations 136 --;9.4 Uniqueness of Solutions 140 --;10 Explicit Relations with Union and Left-Concatenation 146 --;10.2 Properties of Single Explicit Relations in One Variable 149 --;10.3 Solving Systems with Several Explicit Equations for One Variable 151 --;10.4 Solving Strictly Decoupled Systems 159 --;10.5 Solving General Decoupled Systems 162 --;11 Implicit Relations with Union and Left-Concatenation 171 --;11.1 Existence of Solutions 174 --;11.2 Uniqueness of Solutions 177 --;12 Two-Sided Language Equations 184 --;13 Mixed Systems 198 --;13.1 Mixed Systems of Equations with Union and Left-Concatenation 199 --;13.2 Mixed Systems of Equations over a One-Letter Alphabet with Regular Constants and Union, Concatenation, and Star 202 --;14 Open Problems 207 --;14.1 Classification 207 --;14.2 The Cardinality of the Alphabet 208 --;14.3 The Class of Constant Languages 209 --;14.4 The Set of Operations Involved 209 --;14.5 Two-Sided, Implicit, and Explicit Equations 210 --;14.6 Effectiveness of Constructions 211.
|
| Abstract
|
:
|
Presenting a framework for a general theory for solving systems of equations and relations between languages, this book covers classical language equations, generalized derivatives, Boolean language equations, and implicit equations. There is an exploration of mixed systems and open problems.
|
| Subject
|
:
|
Computational linguistics.
|
| Subject
|
:
|
Formale Sprache
|
| Subject
|
:
|
Natural language processing (Computer science)
|
| LC Classification
|
:
|
QA76.9.N38E767 9999
|
| Added Entry
|
:
|
Ernst L Leiss
|
| |