The existential theory of equations with rational constraints in free groups is PSPACE-complete (Q2573633): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / OpenAlex ID
 
Property / OpenAlex ID: W2039800792 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: cs/0103018 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5616207 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3859267 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2762503 / rank
 
Normal rank
Property / cites work
 
Property / cites work: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science / rank
 
Normal rank
Property / cites work
 
Property / cites work: Existential and positive theories of equations in graph products / rank
 
Normal rank
Property / cites work
 
Property / cites work: Solving word equations modulo partial commutations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4535046 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4079524 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Bound on Solutions of Linear Integer Equalities and Inequalities / rank
 
Normal rank
Property / cites work
 
Property / cites work: Monadic simultaneous rigid E-unification and related problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4508394 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Satisfiability of equations in free groups is in PSPACE / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4408477 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5592246 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The expressibility of languages and relations by word equations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of Makanin's algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Makanin's algorithm is not primitive recursive / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3659988 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4146913 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4750010 / rank
 
Normal rank
Property / cites work
 
Property / cites work: DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3699681 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds on the index and period of a binary relation on a finite set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4376064 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5619830 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Satisfiability of word equations with constants is in NEXPTIME / rank
 
Normal rank
Property / cites work
 
Property / cites work: Satisfiability of word equations with constants is in PSPACE / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4219050 / rank
 
Normal rank
Property / cites work
 
Property / cites work: ON SYSTEMS OF EQUATIONS IN A FREE GROUP / rank
 
Normal rank
Property / cites work
 
Property / cites work: Makanin's algorithm for word equations-two improvements and a generalization / rank
 
Normal rank

Latest revision as of 12:17, 11 June 2024

scientific article
Language Label Description Also known as
English
The existential theory of equations with rational constraints in free groups is PSPACE-complete
scientific article

    Statements

    The existential theory of equations with rational constraints in free groups is PSPACE-complete (English)
    0 references
    0 references
    0 references
    0 references
    22 November 2005
    0 references

    Identifiers