All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

A note on limited pushdown alphabets in stateless deterministic pushdown automata

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00394000" target="_blank" >RIV/67985840:_____/13:00394000 - isvavai.cz</a>

  • Result on the web

    <a href="http://dx.doi.org/10.1142/S0129054113500068" target="_blank" >http://dx.doi.org/10.1142/S0129054113500068</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1142/S0129054113500068" target="_blank" >10.1142/S0129054113500068</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    A note on limited pushdown alphabets in stateless deterministic pushdown automata

  • Original language description

    Recently, an infinite hierarchy of languages accepted by stateless deterministic pushdown automata has been established based on the number of pushdown symbols. However, the witness language for the n-th level of the hierarchy is over an input alphabet with 2(n-1) elements. In this paper, we improve this result by showing that a binary alphabet is sufficient to establish this hierarchy. As a consequence of our construction, we solve the open problem formulated by Meduna et al. Then we extend these results to m-state realtime deterministic pushdown automata, for all m at least 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open.

  • Czech name

  • Czech description

Classification

  • Type

    J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

  • CEP classification

    BA - General mathematics

  • OECD FORD branch

Result continuities

  • Project

    <a href="/en/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralized and coordination supervisory control</a><br>

  • Continuities

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Others

  • Publication year

    2013

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Name of the periodical

    International Journal of Foundations of Computer Science

  • ISSN

    0129-0541

  • e-ISSN

  • Volume of the periodical

    24

  • Issue of the periodical within the volume

    3

  • Country of publishing house

    SG - SINGAPORE

  • Number of pages

    10

  • Pages from-to

    319-328

  • UT code for WoS article

    000321428600002

  • EID of the result in the Scopus database