ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
Collection
Publisher
Years
  • 1
    Electronic Resource
    Electronic Resource
    Size, index, and context-sensitivity of controlled partition grammars (1977)
    Springer
    Theory of computing systems 11 (1977), S. 47-60 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Controlled partition grammars (CPGs) were designed to apply to certain needs of linguists. General CPGs generate exactly all context-sensitive languages. CPGs have two parameters:size andindex. The partition index of CPGs can be bounded by two, while CPGs with partition index one generate exactly the class of context-free languages. The size (of the partition blocks) of CPGs can be bounded by two, while CPGs of size one generate a class of languages properly contained in the class of contextsensitive languages. If one can eliminate recursive productions of the formA→B in a CPG then deterministic and nondeterministic lba's are equivalent.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01768467
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On strict interpretations of grammar forms (1978)
    Springer
    Theory of computing systems 12 (1978), S. 233-252 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Strict interpretations of grammar forms are studied with respect to parsing, ambiguity, and decidability for intersection and containment. In particular, a parsing procedure for an arbitrary strict interpretation grammar is given which is based on a given parsing method for the master grammar. Time and space bounds on the new procedure are then obtained. Each ambiguous interpretation grammar of an unambiguous grammar form can be converted to an equivalent unambiguous interpretation of the same grammar form. Unambiguity is always decidable for strict interpretation grammars of unambiguous grammar forms. Also, for languages obtained from “compatible” strict interpretations of an unambiguous grammar form, the following problems are solvable: empty intersection, finite intersection, containment, and equality.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01776576
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On reducing the number of states in a PDA (1981)
    Springer
    Theory of computing systems 15 (1981), S. 315-321 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A transformation is presented which converts any pushdown automaton (PDA)M 0 withn 0 states andp 0 stack symbols into an equivalent PDAM withn states and ⌈n 0 /n⌉2 p 0 stack symbols into an equivalent ofn, 1⩽n〈n 0. This transformation preserves realtime behavior but not derterminism. The transformation is proved to be the best possible one in the following sense: for each choice of the parametersn 0 + 1 stack symbols for any desired value realtime PDAM 0 such that any equivalent PDAM (whether realtime or not) havingn states must have at least ⌈(n 0 /n)2 p0⌉ stack symbols. Furthermore, the loss of deterministic behavior cannot be avoided, since for each choice ofn 0 andp 0, there is a deterministic PDAM 0 such that no equivalent PDAM with fewer states can be deterministic.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01786988
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A note on classes of complements and the LBA problem (1978)
    Springer
    Acta informatica 10 (1978), S. 169-173 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary The complements of an AFL ℒ form an AFL if and only if ℒ is closed under “length-preserving” universal quantification. The complements of the context-sensitive languages form a principal AFL with a hardest set L 1. The context-sensitive languages are closed under complementation if and only if L 1 is context-sensitive.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00289154
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Amounts of nondeterminism in finite automata (1980)
    Springer
    Acta informatica 13 (1980), S. 199-204 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary The amount of nondeterminism in a nondeterministic finite automaton (NFA) is measured by counting the minimal number of “guessing points” a string w has to pass through on its way to an accepting state. NFA's with more nondeterminism can achieve greater savings in the number of states over their deterministic counterparts than NFA's with less nondeterminism. On the other hand, for some nontrivial infinite regular languages a deterministic finite automaton (DFA) can already be quite succinct in the sense that NFA's need as many states (and even context-free grammars need as many nonterminals) as the minimal DFA has states.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00263994
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On reducing the number of stack symbols in a PDA (1993)
    Springer
    Theory of computing systems 26 (1993), S. 313-326 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Two transformations are presented which, for any pushdown automaton (PDA)M withn states andp stack symbols, reduce the number of stack symbols to any desired numberp′ greater than one. The first transformation preserves deterministic behavior and produces an equivalent PDA witho(np/p′) states. The second construction, using a technique which introduces nondeterminism, produces an equivalent PDA withO(n√p/p′) states. Both transformations are essentially optimal, the former among determinism-preserving transformations, the latter among all transformations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189852
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Concise representations of regular languages by degree and probabilistic finite automata (1993)
    Springer
    Theory of computing systems 26 (1993), S. 379-395 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Meyer and Fischer b][MF] proved that nondeterministic finite automata (NFA) can be exponentially more concise than deterministic finite automata (DFA) in their representations of regular languages. Several variants of that basic finite state machine model are now being used to analyze parallelism and to build real-time software systems [HL+]. Even though these variants can sometimes represent regular languages in a more concise manner than NFA, the underlying models fundamentally differ from NFA in how they operate. Degree automata [W] (DA), however, differ from NFA only in their acceptance criteria and accept only regular languages. We show here that DA are also exponentially more concise than NFA on some sequences of regular languages. We also show that the conciseness of probabilistic automata [R] with isolated cutpoints can be unbounded over DA and, concurrently, i.e., over the same sequence of languages, those DA can be exponentially more concise than NFA.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...