article

Extended finite automata over groups

Authors:

Victor Mitrana,

Ralf StiebeAuthors Info & Claims

Discrete Applied Mathematics, Volume 108, Issue 3

Pages 287 - 300

https://doi.org/10.1016/S0166-218X(00)00200-6

Published: 15 March 2001 Publication History

Abstract

No abstract available.

Cited By

View all

Yuyama T(2023)Groups Whose Word Problems Are Accepted by Abelian -AutomataDevelopments in Language Theory10.1007/978-3-031-33264-7_20(246-257)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33264-7_20
Zetzsche G(2021)Recent Advances on Reachability Problems for Valence Systems (Invited Talk)Reachability Problems10.1007/978-3-030-89716-1_4(52-65)Online publication date: 25-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89716-1_4
Fernau HParamasivan MSchmid MVorel V(2017)Characterization and complexity results on jumping finite automataTheoretical Computer Science10.1016/j.tcs.2016.07.006679:C(31-52)Online publication date: 30-May-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.07.006
Show More Cited By

Index Terms

Extended finite automata over groups
1. Theory of computation
  1. Logic
  2. Models of computation
    1. Computability

Recommendations

On input-revolving deterministic and nondeterministic finite automata

We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to ...
Reversible pushdown automata

Reversible pushdown automata are deterministic pushdown automata that are also backward deterministic. Therefore, they have the property that any configuration occurring in any computation has exactly one predecessor. In this paper, the computational ...
Closure properties of cellular automata

Concerning the power of one-dimensional cellular automata recognizers, Ibarra and Jiang have proved that real time cellular automata (CA) and linear time CA are equivalent if and only if real time CA is closed under reverse. In this paper we investigate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 108, Issue 3

March 15, 2001

119 pages

ISSN:0166-218X

Editor:
Peter L. Hammer

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 15 March 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yuyama T(2023)Groups Whose Word Problems Are Accepted by Abelian -AutomataDevelopments in Language Theory10.1007/978-3-031-33264-7_20(246-257)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33264-7_20
Zetzsche G(2021)Recent Advances on Reachability Problems for Valence Systems (Invited Talk)Reachability Problems10.1007/978-3-030-89716-1_4(52-65)Online publication date: 25-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89716-1_4
Fernau HParamasivan MSchmid MVorel V(2017)Characterization and complexity results on jumping finite automataTheoretical Computer Science10.1016/j.tcs.2016.07.006679:C(31-52)Online publication date: 30-May-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.07.006
Zetzsche G(2013)Silent transitions in automata with storageProceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-39212-2_39(434-445)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39212-2_39
Cadilhac MFinkel AMcKenzie P(2012)Unambiguous constrained automataProceedings of the 16th international conference on Developments in Language Theory10.1007/978-3-642-31653-1_22(239-250)Online publication date: 14-Aug-2012
https://dl.acm.org/doi/10.1007/978-3-642-31653-1_22
Zetzsche G(2011)On the capabilities of grammars, automata, and transducers controlled by monoidsProceedings of the 38th international conference on Automata, languages and programming - Volume Part II10.5555/2027223.2027245(222-233)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027223.2027245
Fernau HStiebe R(2011)On the expressive power of valences in cooperating distributed grammar systemsComputation, cooperation, and life10.5555/2017728.2017739(90-106)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2017728.2017739
Render EKambites M(2009)Rational subsets of polycyclic monoids and valence automataInformation and Computation10.1016/j.ic.2009.02.012207:11(1329-1339)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1016/j.ic.2009.02.012
Render EKambites M(2008)Polycyclic and Bicyclic Valence AutomataLanguage and Automata Theory and Applications10.1007/978-3-540-88282-4_42(464-475)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-88282-4_42
Kambites M(2006)Word problems recognisable by deterministic blind monoid automataTheoretical Computer Science10.1016/j.tcs.2006.06.026362:1(232-237)Online publication date: 11-Oct-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.06.026
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

On input-revolving deterministic and nondeterministic finite automata

Reversible pushdown automata

Closure properties of cellular automata

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations