分解
发表于 2025-3-28 17:34:40
Minimization of Non-deterministic Automata with Large Alphabetss the one suggested by Paige and Tarjan. The algorithm has a complexity of .(. log .) where . is the number of edges and . is the number of states in the automaton. A bottleneck in the application of the algorithm is often the number of labels which may appear on the edges of the automaton. In this
伟大
发表于 2025-3-28 19:05:00
Simulating Two-Dimensional Recognizability by Pushdown and Queue Automataer to encompass a wider class of languages. We show that any (tiling) recognizable language can be simulated by a 4NFA with an extra queue whose size is bounded by the minimum of the two dimensions of a picture; and that 2NFA (i.e. automata moving only in two directions) with an analogous queue are
石墨
发表于 2025-3-28 23:04:59
http://reply.papertrans.cn/47/4626/462537/462537_43.png
时代
发表于 2025-3-29 05:02:14
http://reply.papertrans.cn/47/4626/462537/462537_44.png
Aggressive
发表于 2025-3-29 07:39:55
Prime Normal Form and Equivalence of Simple Grammarsl time if a language generated by a simple context-free grammar is a prime. Our algorithm computes a canonical representation of a simple language, converting its arbitrary simple grammar into Prime Normal Form (PNF); a simple grammar is in PNF if all its nonterminals define primes. We also improve
BOLT
发表于 2025-3-29 11:37:05
An Incremental Algorithm for Constructing Minimal Deterministic Finite Cover Automata less states than the DFA for ., this technique seems to be the best choice for incrementally building the automaton for a large language, especially when the number of states in the DFCA is significantly less than the number of states in the corresponding minimal DFA. We have implemented the propos
CODE
发表于 2025-3-29 19:34:37
Finite Automata and Unions of Regular Patterns with Bounded Constant Segmentsse, no efficient algorithm that performs the inference of this class of languages is known. We propose a solution to this problem using the existing connexion between the positive variety of languages of dot depth 1/2, . and the class of unbounded union of pattern languages ..
乐章
发表于 2025-3-29 22:31:00
Inside Vaucansontient, conversion of a regular expression into a weighted automaton, and composition). We explain how complex declarations due to the generic programming are masked from the user and finally we present a proposal for an XML format that allows implicit descriptions for simple types of automata.
arousal
发表于 2025-3-30 00:00:33
Deterministic Recognition of Trees Accepted by a Linear Pushdown Tree AutomatonDTAs) is proposed. L-PDTAs accept an important class of tree languages since the class of their yield languages coincides with the class of yield languages generated by tree adjoining grammars (TAGs). The proposed algorithm is obtained by combining a bottom-up parsing procedure on trees with the CKY
emission
发表于 2025-3-30 06:26:42
Shorter Regular Expressions from Finite-State Automatave method for computing regular expressions from finite-state automata, the resulting regular expressions are often very long and complicated. We examine the minimization of finite-state automata to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and hor