Detail publikace

Rewriting Systems with Restricted Configurations

Originální název

Rewriting Systems with Restricted Configurations

Anglický název

Rewriting Systems with Restricted Configurations

Jazyk

en

Originální abstrakt

This theoretically oriented dissertation discusses rewriting systems, including various automata and grammars.  It concentrates its attention upon their combination.  More specifically, the central role of the present dissertation plays the general notion of a configuration as an instantaneous description of a rewriting system.  Based upon various restrictions placed upon configurations and rewriting modes, the systems are classified and studied. Apart from this major topic, the dissertation also discusses dynamic complexity, which is based upon metrics placed upon the process of yielding strings.     As its fundamental topic, the dissertation discusses #-rewriting system,  reducing deep pushdown automaton, and pushdown automata with restricted pushdowns. In addition, it studies some variants of #-rewriting systems, including n-right linear and generalized #-rewriting system.  In general, the dissertation demonstrates how the generative power of the systems under discussion depends upon the restrictions placed upon them. In terms of dynamic complexity, it discusses a close relationship between various rewriting systems, including newly introduced systems.  As its main result, the dissertation demonstrates several infinite hierarchies of language families defined by rewriting systems in dependency on their restrictions.          The conclusion demonstrates the application-important properties of the systems discussed in the dissertation. It sketches two new types of determinism and canonical rewriting; then, it demonstrates their potential practical usage.

Anglický abstrakt

This theoretically oriented dissertation discusses rewriting systems, including various automata and grammars.  It concentrates its attention upon their combination.  More specifically, the central role of the present dissertation plays the general notion of a configuration as an instantaneous description of a rewriting system.  Based upon various restrictions placed upon configurations and rewriting modes, the systems are classified and studied. Apart from this major topic, the dissertation also discusses dynamic complexity, which is based upon metrics placed upon the process of yielding strings.     As its fundamental topic, the dissertation discusses #-rewriting system,  reducing deep pushdown automaton, and pushdown automata with restricted pushdowns. In addition, it studies some variants of #-rewriting systems, including n-right linear and generalized #-rewriting system.  In general, the dissertation demonstrates how the generative power of the systems under discussion depends upon the restrictions placed upon them. In terms of dynamic complexity, it discusses a close relationship between various rewriting systems, including newly introduced systems.  As its main result, the dissertation demonstrates several infinite hierarchies of language families defined by rewriting systems in dependency on their restrictions.          The conclusion demonstrates the application-important properties of the systems discussed in the dissertation. It sketches two new types of determinism and canonical rewriting; then, it demonstrates their potential practical usage.

BibTex


@book{BUT61938,
  author="Zbyněk {Křivka}",
  title="Rewriting Systems with Restricted Configurations",
  annote="This theoretically oriented dissertation discusses rewriting systems, including
various automata and grammars.  It concentrates its attention upon their
combination.  More specifically, the central role of the present dissertation
plays the general notion of a configuration as an instantaneous description of
a rewriting system.  Based upon various restrictions placed upon configurations
and rewriting modes, the systems are classified and studied. Apart from this
major topic, the dissertation also discusses dynamic complexity, which is based
upon metrics placed upon the process of yielding strings.

    As its fundamental topic, the dissertation discusses #-rewriting system, 
reducing deep pushdown automaton, and pushdown automata with restricted
pushdowns. In addition, it studies some variants of #-rewriting systems,
including n-right linear and generalized #-rewriting system.  In general, the
dissertation demonstrates how the generative power of the systems under
discussion depends upon the restrictions placed upon them. In terms of dynamic
complexity, it discusses a close relationship between various rewriting systems,
including newly introduced systems.  As its main result, the dissertation
demonstrates several infinite hierarchies of language families defined by
rewriting systems in dependency on their restrictions.
    
    The conclusion demonstrates the application-important properties of the
systems discussed in the dissertation. It sketches two new types of determinism
and canonical rewriting; then, it demonstrates their potential practical usage.",
  address="Faculty of Information Technology BUT",
  chapter="61938",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Faculty of Information Technology BUT",
  year="2008",
  month="october",
  pages="0--0",
  publisher="Faculty of Information Technology BUT",
  type="book"
}